[jimmyvan]

datatype 'a tree= Leaf of 'a | Node of 'a tree * 'a * 'a tree

fun binSearch (Node(left,n,right)) x =

if x > n then false

else if x=n then true

else binSearch (Node(left,n,right)) x = binSearch (right) x andalso binSearch (left) x;

Ktoś pomoże? Co jest tutaj złego? ;/
Działa dla:

binSearch (Node (Node (Leaf 1, 2, Leaf 3), 4, Leaf 7)) 7;

nie działa dla:

binSearch (Node (Node (Leaf 1, 2, Leaf 3), 4, Leaf 7)) 2;

#programowaniefunkcyjne #programowanie #sml

[tell_me_more]

@jimmyvan: ostatnio używałem sml z 10 lat temu, ale jeśli dobrze pamiętam składnie i rozumiem to dla przypadku x>n zwracasz od razu false, nawet, jak to jest nie liść. Czemu? Przecież x może wtedy i tak być w prawym poddrzewie?

I chyba zamieniłeś przykłady, kiedy działa, a kiedy nie działa? Albo znak ">" w kodzie był odwrotnie?

I dlaczego andalso? True chcesz zwracać tylko, jak w obu poddrzewach jest element?

Jak

[jimmyvan]

@tell_me_more: to już działa; zakłada się, że liczby się nie powtarzają. pozdro

 fun binSearch (t:int tree) (x:int) =
 case t of
 Leaf l => l=x
 | Node (l,v,r) =>
 if x=v then true
 else if x<v then binSearch l x
 else binSearch r x

[FaraonMerJan]

@jimmyvan: działa także wtedy, gdy liczby się powtarzają ( ͡° ͜ʖ ͡°)
Sprawdź na rysunku.

[jimmyvan]

@FaraonMerJan: ciekawe, czy da się zrobić to bez case'a

[FaraonMerJan]

@jimmyvan: możesz pewnie jakoś naśladować case'a ifami, tylko po co? Pattern matching jest czymś bardzo naturalnym w programowaniu funkcyjnym.

[jimmyvan]

@FaraonMerJan: dopiero zaczynam naukę sml'a i właśnie poznałem case'a - nie mam jeszcze czystej idei programowania funkcyjnego ;p

[FaraonMerJan]

@jimmyvan: co daje case ponad ify?
Powiedzmy, że masz typ Shape, który może oznaczać przeróżne kształty i masz też funkcję area, która liczy pole kształtu.
Jeśli dodasz na przykład koło do typu Shape, to w przypadku ifów można łatwo przeoczyć to, że nie rozszerzyłeś funkcji area o liczenie pola koła. Jeśli funkcja area ma w sobie case, to kompilator powinien jakoś ostrzec, że nie wszystkie kształty są obsługiwane.

[woljako]

złożoność n*k?