[haskell]functie uitzoeken voor schoolopdracht

[KillerZero86]

Voor een schoolopdracht wordt ik geacht erachter te komen wat de volgende functie doet:

code:

sbt _ NullNode = Nothing
sbt key (Node nodeKey nodeValue (leftChild, rightChild)) =
case compare key nodeKey of
LT -> sbt key leftChild
GT -> sbt key rightChild
EQ -> Just nodeValue

In bovenstaande functie zijn:
• _: een variabele, waarvan de waarde ons niet interesseert
• LT, GT en EQ: lower than, greater than en equal
• compare: vergelijkt 2 waarden

Ikzelf heb nog nooit Haskell gehad en na anderhalf uur puzzelen heb ik besloten het hier neer te leggen. Zelf ben ik alleen bedreven met OO talen, dus misschien is mijn hele denkwijze wel fout.

Mijn begrjiping hiervan:
Op de eerste regel wordt functie sbt aangeroepen met als parameters _ en NullNode. Nullnode heeft als waarde null.
Vanaf regel twee begint de functie sbt. sbt neemt twee parameters eentje ongedefinieerd genaamd key en een node. Deze node is kennelijk een soort object en bevat een nodekey, een nodevalue, een rightChild en een leftChild. Vervolgens wordt er een vergelijking uitgevoerd tussen de key en de node (dat kan kennelijk). If key < node gebruik leftChild om hetzelfde nog eens te doen, if key > node gebruik rightChild om nog eens hetzelfde te doen en anders return nodevalue.

Klopt dit ook maar enigszinds met wat hier staat?

[Moluh]

Lijkt me in grote lijnen best ok. In Haskell kan je dezelfde functie meerdere keren definieren met verschillende parameters. Er wordt gekeken welke definitie matched met wat er gegeven wordt en kiest de juiste

sbt _ NullNode = Nothing
sbt key (some other datastruct) = ...
Dus beide zijn functiedefinities.
Als de tweede param NullNode is, is het resultaat Nothing (niet echt null).
Als het geen nullnode is maar een (Node key value (left, right)) gaan we de case of in en idd zoeken links, rechts, gevonden.
De oorspronkelijke datastruct is waarschijnlijk data Boom = NullNode | Node Int Int (Boom Boom)
Just en Nothing zijn veelgebruikt en onderdeel van: data Maybe = Just a | Nothing. Hiermee kan je aangeven of hetgene wat je wilde is gelukt (vinden van een element). In Java oid zie je idd vaak return null, return -1, ...

~edit
http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf
http://book.realworldhaskell.org/
zijn redelijke resources.

[ Voor 6% gewijzigd door Moluh op 11-07-2012 16:26 ]

[Soultaker]

KillerZero86 schreef op woensdag 11 juli 2012 @ 16:11:
Op de eerste regel wordt functie sbt aangeroepen met als parameters _ en NullNode. Nullnode heeft als waarde null.
Vanaf regel twee begint de functie sbt.

Dit klopt niet; ook de eerste regel is onderdeel van de functiedefinitie.

Pattern matching in parameters is vergelijkbaar met pattern matching met case .. of die je al in de tweede definitie ziet. Je zou de hele functie dus ook kunnen schrijven als:

Haskell:

sbt key node = case node of
  NullNode -> Nothing
  Node nodeKey nodeValue (leftChild, rightChild) -> case compare key nodeKey of
    LT -> sbt key leftChild
    GT -> sbt key rightChild
    EQ -> Just nodeValue

Deze node is kennelijk een soort object en bevat een nodekey, een nodevalue, een rightChild en een leftChild.

Dit klopt. Node is een constructor van een algebraïsch datatype (en NullNode is de andere constructor).

Vervolgens wordt er een vergelijking uitgevoerd tussen de key en de node (dat kan kennelijk).

Niet key en node, maar key en de nodeKey.

De rest klopt wel aardig. (Zie ook Moluh's reactie.) Voor het geval het nog niet duidelijk is: de functie doet een lookup in een binary search tree (en sbt zal wel voor search binary tree staan).

[KillerZero86]

Aah, bedankt mensen! Het is me nu eindelijk duidelijk hoe het programma werkt, hoewel ik nog niet in staat zou zijn het programma na te bouwen. Enig puntje wat me nog ontgaat is: wat doet die _ precies in het programma?

[ Voor 20% gewijzigd door KillerZero86 op 11-07-2012 19:48 ]

[kutagh]

Die '_' is gewoon een placeholder: Hier zit er een variabele waar ik geen interesse in heb.

[eamelink]

KillerZero86 schreef op woensdag 11 juli 2012 @ 19:47:
Aah, bedankt mensen! Het is me nu eindelijk duidelijk hoe het programma werkt, hoewel ik nog niet in staat zou zijn het programma na te bouwen. Enig puntje wat me nog ontgaat is: wat doet die _ precies in het programma?

Die zit in de pattern match waarbij de node een NullNode is. Als dat het geval is, ben je niet geinteresseerd in de key, dus hoef je die ook geen naam te geven. Dan gebruik je _.

[bwerg]

Waarschuwing: ik heb nog nooit haskell geprogrammeerd, wel een andere functionele taal (clean, lijkt er erg op dus ik neem aan dat mijn antwoord alsnog volledig klopt, op wat syntax na misschien).
Wordt er geen type van de functie bij gegeven? Daarin staan wat voor type "parameters" verwacht worden, en welk type er opgeleverd wordt. Niet altijd noodzakelijk, maar voor het begrip wel handig.
Ter vergelijking, een typering van een functie is in een procedurele taal is iets als (als er gegeven een int en een String, als resultaat een int gegeven wordt):

code:

int doSomething(int input1, String input2)

en in een functionele taal is dat iets als (dit wordt vaak boven de functie gezet, zo niet dan heeft je functie impliciet alsnog zo'n type):

code:

doSomething :: int String -> int

De functie zelf beschrijf je daarna met pattern-matching:

code:

doSomething x "verhogen" = x+1
doSomething x "keer drie" = 3*x

En als een parameter je in een bepaald geval niet gebruikt in het resultaat hoef je daar toch niet naar te verwijzen, dus geef je geen naam maar noem je die dus "_":

code:

doSomething _ "nul" = 0

Beetje raar trouwens dat je niet eens uitgelegd krijg hoe een functionele taal werkt, en je dan al met recursie door bomen moet werken.

[ Voor 5% gewijzigd door bwerg op 13-07-2012 12:55 ]