[Haskell] Unieke waarden in 2 lists vinden

[st0p]

Eindelijk ben ik eens begonnen met serieus wat tijd in functioneel programmeren te steken. Hoewel ik niet kan zeggen dat ik het al helemaal begrijp is het tot op heden erg cool!

Mijn eigen experimenten hebben me onder andere de volgende code opgeleverd (dit doet verder nog niks nuttigs, het zijn slechts beginnersstapjes)

code:

modList xs m = [x | x <- xs, x `mod` m == 0]

intersect xs ys = [x | x <- xs, y <- ys, x == y]

dit geeft in ghci de volgende resultaten:

code:

*Main> let list3 = modList [0..100] 3
*Main> let list5 = modList [0..100] 5
*Main> let intersection = intersect list3 list5
*Main> list3
[0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99]
*Main> list5
[0,5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100]
*Main> intersection
[0,15,30,45,60,75,90]

Zoals je kan zien geeft de functie intersection alleen de waarden terug die in beide lists voorkomen. Maar hoe zou ik een functie kunnen schrijven die een list returnt met de waarden die maar in een van beide lists voorkomt? Niet dat dit een perse heel handige functie, maar het is gewoon uit beginners interesse dat ik deze vraag stel.

Volgens mij moet ik meerdere list comprehensions met elkaar combineren, maar ik zie zo 123 niet hoe ik dt moet doen.

[roy-t]

Ik zou het in twee delen doen, eerst lijst 1 kopieren en dan lijst 2 elk element toevoegen als contains == false.

Mijn Haskell is een beetje roestig (alweer een jaar geleden dat ik dat gedaan heb). Maar zoiets?

Haskell:

combine xs ys = xs ++ [y | y <-ys, not (contains xs y)]

contains (x:xs) y
contains [] y = false
  | x == y = true
  | x != y = contains xs ys

Waarschijnlijk compileert dit niet helemaal, maar je begrijpt het idee wel

Edit: nog even wat syntax opgezocht, zo klopt het beter.

[ Voor 14% gewijzigd door roy-t op 12-06-2010 14:03 ]

[st0p]

roy-t schreef op zaterdag 12 juni 2010 @ 13:48:
Waarschijnlijk compileert dit niet helemaal, maar je begrijpt het idee wel

Ik begrijp het niet helemaal, maar dat komt omdat ik echt nog een totale n00b ben wbt FP. Ik ga sowieso even stoeien met de code die je gepost hebt, maar als ik de volgende regel goed lees:

code:

combine xs ys = xs ++ [y | y <-ys, not (contains xs y)]

dan wordt bij een

code:

combine list3 list5

de volledige list3 gematched. Dat is niet helemaal wat ik wil, ik wil de waarden die in of in list3 of in list5 voorkomen hebben, maar juist niet de waarden die in beide voorkomen...

Anyway, ik ga het ff proberen.

[roy-t]

st0p schreef op zaterdag 12 juni 2010 @ 13:58:
[...]


Ik begrijp het niet helemaal, maar dat komt omdat ik echt nog een totale n00b ben wbt FP. Ik ga sowieso even stoeien met de code die je gepost hebt, maar als ik de volgende regel goed lees:

code:

combine xs ys = xs ++ [y | y <-ys, not (contains xs y)]

dan wordt bij een

code:

combine list3 list5

de volledige list3 gematched. Dat is niet helemaal wat ik wil, ik wil de waarden die in of in list3 of in list5 voorkomen hebben, maar juist niet de waarden die in beide voorkomen...

Anyway, ik ga het ff proberen.

Oh pardon je wilt de waarden hebben die niet in beiden voorkomen. Nu krijg je de waarden die in A of in B voorkomen maar slechts 1 keer als ze in beiden lijsten voorkomen.

Anyway, nu je eenmaal contains hebt is dit makkelijk op te lossen

Haskell:

Intersect xs ys  = [x | x <- xs, contains ys x]

Haskell:

Difference xs ys = [x | x <- xs, not (contains ys x)] ++ [y | y <- ys, not (contains xs y)]

[ Voor 19% gewijzigd door roy-t op 12-06-2010 14:13 ]

[RayNbow]

roy-t schreef op zaterdag 12 juni 2010 @ 13:48:
Ik zou het in twee delen doen, eerst lijst 1 kopieren en dan lijst 2 elk element toevoegen als contains == false.

Mijn Haskell is een beetje roestig (alweer een jaar geleden dat ik dat gedaan heb). Maar zoiets?

Haskell:

combine xs ys = xs ++ [y | y <-ys, not (contains xs y)]

contains (x:xs) y
contains [] y = false
  | x == y = true
  | x != y = contains xs ys

Waarschijnlijk compileert dit niet helemaal, maar je begrijpt het idee wel

Edit: nog even wat syntax opgezocht, zo klopt het beter.

Ten eerste, de Prelude bevat de functies elem en notElem. Je hoeft dus geen eigen contains functie te schrijven.
Ten tweede, ongelijkheid in Haskell is /=, niet !=.

st0p schreef op zaterdag 12 juni 2010 @ 13:27:
Eindelijk ben ik eens begonnen met serieus wat tijd in functioneel programmeren te steken. Hoewel ik niet kan zeggen dat ik het al helemaal begrijp is het tot op heden erg cool!

Mijn eigen experimenten hebben me onder andere de volgende code opgeleverd (dit doet verder nog niks nuttigs, het zijn slechts beginnersstapjes)

code:

modList xs m = [x | x <- xs, x `mod` m == 0]

intersect xs ys = [x | x <- xs, y <- ys, x == y]

dit geeft in ghci de volgende resultaten:

code:

*Main> let list3 = modList [0..100] 3
*Main> let list5 = modList [0..100] 5
*Main> let intersection = intersect list3 list5
*Main> list3
[0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99]
*Main> list5
[0,5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100]
*Main> intersection
[0,15,30,45,60,75,90]

Zoals je kan zien geeft de functie intersection alleen de waarden terug die in beide lists voorkomen.

Misschien is dit een mooiere intersect functie?
(Die ook nog alle dubbelen weghaalt)

Haskell:

import Data.List
intersect xs ys = nub [x | x <- xs, x `elem` ys]

Maar hoe zou ik een functie kunnen schrijven die een list returnt met de waarden die maar in een van beide lists voorkomt? Niet dat dit een perse heel handige functie, maar het is gewoon uit beginners interesse dat ik deze vraag stel.

Volgens mij moet ik meerdere list comprehensions met elkaar combineren, maar ik zie zo 123 niet hoe ik dt moet doen.

Als je lijst A en lijst B hebt, wil je dan de items die in A en in B voorkomen, maar niet in beide?

[st0p]

edit:
Roy-t, niet je post zo radicaal editen

check mijn oorspronkelijke code eens, ik heb al een intersect geschreven

difference en union waren idd de termen die ik zocht. That brings back memories to pov-ray

De code die je gepost hebt compiled bij mij niet, heb zelf ook pas net 2 uur geleden over pattern matching en guards voor functies gelezen, dus het is nog even puzzelen hoe ik dat aan de praat moet krijgen. Als ik het werkend heb zal ik hier de resultaten posten (laat me maar ff aankloten ipv hier code posten die wel compiled, daar leer ik alleen maar van.)

Dan nog vraag ik me af of het met een ingewikkelder list comprehension niet in een functie te vatten is, maar algorhythmisch gesproken heb je gelijk dat jouw oplossing ook valide is.

@Roy-t:

code:

Difference xs ys = [x | x <- xs, not (contains ys x)] ++ [y | y <- ys, not (contains xs y)]

Lijkt mij correct, maar ik heb het nog niet uitgeprobeerd (was nog bezig met die contains functie aan de praat krijgen)

@Raynbow:

Ten eerste, de Prelude bevat de functies elem en notElem. Je hoeft dus geen eigen contains functie te schrijven.

notElem kende ik nog niet, bedankt! Dat neemt niet weg dat het vanuit educatief oogpunt geen kwaad kan om die contains functie aan de praat te krijgen.

code:

import Data.List
intersect xs ys = nub [x | x <- xs, x `elem` ys]

import heb ik wel voorbij zien komen maar nog helemaal niet gebruikt, maar inderdaad is die nub een mooiere oplossing.

Je gebruik van elem hier is very nice, dat had ik zelf nog niet verzonnen. Ik ga ervan uit dat mijn oude x == y oplossing een artefact is van vele jaren imperatief / OO programmeren Als ik het goed begrijp heeft jouw oplossing nog een klein marginaal performance voordeel vanwege lazy evaluation, of vergis ik me dan?

[ Voor 44% gewijzigd door st0p op 12-06-2010 14:42 ]

[roy-t]

@RayNbow, het is alweer een jaar geleden dat ik gespeeld heb de code was ook maar meer ter illustratie . Btw wat is "nub" voor een functie?

@st0p, goede instelling!

Wat betreft algorythmisch gezien, tijdscomplexiteit is in Haskell altijd wat ingewikkeld, (vooral ook omdat je met oneindige lijsten kan werken). Maar toch schat ik dat dit algoritme inderdaad n^2 is. Als je de lijst sorteert kun je dit natuurlijk veel sneller doen.

[ Voor 4% gewijzigd door roy-t op 12-06-2010 14:32 ]

[st0p]

roy-t schreef op zaterdag 12 juni 2010 @ 14:31:
Wat betreft algorythmisch gezien, tijdscomplexiteit is in Haskell altijd wat ingewikkeld, (vooral ook omdat je met oneindige lijsten kan werken). Maar toch schat ik dat dit algoritme inderdaad n^2 is. Als je de lijst sorteert kun je dit natuurlijk veel sneller doen.

Het gaat me uiteindelijk niet eens zozeer om performance, maar ik lees overal dat FP beknopte en bondige code oplevert. Aangezien dit geen productie code is, probeer ik ook uit te zoeken hoe ik het zo kort mogelijk kan doen. Als het wel productie code was geweest was leesbaarheid een belangrijker argument.

[RayNbow]

st0p schreef op zaterdag 12 juni 2010 @ 14:21:
@Raynbow:

[...]


notElem kende ik nog niet, bedankt! Dat neemt niet weg dat het vanuit educatief oogpunt geen kwaad kan om die contains functie aan de praat te krijgen.

code:

import Data.List
intersect xs ys = nub [x | x <- xs, x `elem` ys]

import heb ik wel voorbij zien komen maar nog helemaal niet gebruikt, maar inderdaad is die nub een mooiere oplossing.

Je gebruik van elem hier is very nice, dat had ik zelf nog niet verzonnen. Ik ga ervan uit dat mijn oude x == y oplossing een artefact is van vele jaren imperatief / OO programmeren Als ik het goed begrijp heeft jouw oplossing nog een klein marginaal performance voordeel vanwege lazy evaluation, of vergis ik me dan?

Het voordeel van elem is dat deze functie niet per se de gehele lijst hoeft te checken. Als hij een gelijk element gevonden heeft, kan de functie stoppen. Jouw aanpak loopt telkens voor elk element in de eerste lijst de gehele tweede lijst af. Qua complexiteit maakt het echter niets uit.

Om je eigen aanpak beter te leren begrijpen, bestudeer eens wat er in de volgende situatie gebeurt:

Haskell:

let {xs = [1,1]; ys = [1,1,1,1]}   in   [x | x <- xs, y <- ys, x == y]

roy-t schreef op zaterdag 12 juni 2010 @ 14:31:
@RayNbow, het is alweer een jaar geleden dat ik gespeeld heb de code was ook maar meer ter illustratie . Btw wat is "nub" voor een functie?

Nub is een Engels zelfstandig naamwoord dat o.a. het volgende kan betekenen:
[list]
• the essence;
• the core.

In Haskell is het een functie die dubbele items uit een lijst haalt. Het is echter geen efficiente functie (kwadratische complexiteit).

[st0p]

De oplossing is geworden:

code:

difference xs ys = [x | x <- xs, notElem x ys] ++ [y | y <- ys, notElem y xs]

@Roy-t:
Dit is mijn variant op contains geworden:

code:

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys) = if x == y then True else elem' x ys

@Raynbow:

Het voordeel van elem is dat deze functie niet per se de gehele lijst hoeft te checken. Als hij een gelijk element gevonden heeft, kan de functie stoppen. Jouw aanpak loopt telkens voor elk element in de eerste lijst de gehele tweede lijst af. Qua complexiteit maakt het echter niets uit.

Dat bedoelde ik inderdaad met marginaal performance voordeel, alhoewel dat marginaal natuurlijk van de context afhangt.

code:

let {xs = [1,1]; ys = [1,1,1,1]}   in   [x | x <- xs, y <- ys, x == y]

Versus

code:

let {xs = [1,1]; ys = [1,1,1,1]}   in   [x | x <- xs, elem x ys]

Wat ik me dan weer niet gerealiseerd had is dat het hebben van dubbelen dus inderdaad wel een factor is bij de keuze tussen het eerste code fragment en het tweede...

[RayNbow]

st0p schreef op zaterdag 12 juni 2010 @ 20:44:
Dit is mijn variant op contains geworden:

code:

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys) = if x == y then True else elem' x ys

Probeer if-then-else te vermijden als het kan. Zeker wanneer je een boolean constante gebruikt.

Een kleine verbetering zou zijn:

Haskell:

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys) = x == y || elem' x ys

De definitie van elem volgens The Haskell 98 Report is trouwens:

Haskell:

elem x = any (== x)

Edit:

st0p schreef op zaterdag 12 juni 2010 @ 20:44:
De oplossing is geworden:

code:

difference xs ys = [x | x <- xs, notElem x ys] ++ [y | y <- ys, notElem y xs]

Alternatief zonder list comprehensions (en ietsjes korter):

Haskell:

symdiff xs ys = filter (`notElem` ys) xs ++ filter (`notElem` xs) ys

Ik noem de functie hier trouwens symdiff omdat het hier om het symmetrische verschil gaat.

[ Voor 27% gewijzigd door RayNbow op 13-06-2010 14:06 ]

[st0p]

grappig, ik ben nu over filter aan het lezen en realiseerde me dat het inderdaad ook met filter moet kunnen.

mijn elem' functie is trouwens nu:

code:

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys) 
    | x == y = True
    | otherwise = elem' x ys

code:

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys) = x == y || elem' x ys

war doet die ||? Dat is namelijk een notatie die ik nog niet eerder ben tegengekomen...

[ Voor 3% gewijzigd door st0p op 20-06-2010 12:48 ]

[RayNbow]

|| is de logische-of operator.

Haskell:

(||)  ::  Bool -> Bool -> Bool
True  || _  =  True
False || x  =  x

[st0p]

Duhhh... dat had ik zelf moeten kunnen verzinnen. Ik heb hem alleen nog nooit zo voorbij zien komen.

Tenzij je natuurlijk iets als dit hebt in een imperatieve taal:

code:

if (foo() || bar()) {
...
}

Dat is overigens iets wat ik altijd als niet okay heb beschouwd, juist omdat je niet zeker weet dat de 2e functie aangeroepen wordt. Maar als functies geen side-effects hebben is dat natuurlijk opeens geen issue meer.

[roy-t]

sowieso zijn conditional statements met side effects echt not done .

[st0p]

dat zeg ik toch