I am having somewhat unclear understanding of Ocaml Map and Set.s and how to properly think about fold with these structures, I have tried reading blogs online, yet most blogs on Ocaml talks about fold with List . And Have not found a clear and concise blog on Set and Map and their respective fold abilities and or examples .
Thank You
Calling the fold functions for a Map or Set is like building a list of all the elements in the structure and then calling List.fold_right on the list.
For example, if you’ve instantiated Set with the element type String:
module StringSet = Set.Make(String)
and built a set with the values "a", "bc", "def" and "g":
let ss = StringSet.of_list ["a"; "bc"; "def"; "g"];;
then you can concatenate all the elements together by calling StringSet.fold:
# StringSet.fold (fun x y -> x ^ "," ^ y) ss "end";;
- : string = "g,def,bc,a,end"
or by first converting to a list and then calling fold_right on the list:
# let list = StringSet.elements ss;;
val list : StringSet.elt list = ["a"; "bc"; "def"; "g"]
# List.fold_right (fun x y -> x ^ "," ^ y) ["a"; "bc"; "def"; "g"] "end";;
- : string = "a,bc,def,g,end"
(The only difference — apart from the fact that calling fold directly rather than converting to a list is more efficient — is in the order that the elements are passed to the function; see the documentation for more details.)
thank you, what about folding on a Map because Maps have the key,'a ,and 'a t , the documentation on fold for map is so succinct that a novice such as me is not able to decipher the documentation properly . Lets say a map of graph, like a color graph. ?
Suppose you have a map with the entries:
k1, v1
k2, v2
k3, v3
The documentation is saying that:
fold f map initial
is equal to
f k3 v3 (f k2 v2 (f k1 v1 initial))
As you can imagine, the function call series grows with the size of the map.
Thank You, for fold with Map the documentation is
let rec fold f m accu =
** match m with**
** Empty -> accu**
** | Node {l; v; d; r} ->**
** fold f r (f v d (fold f l accu))**
I am still somewhat unclear on how to use fold with Map, maybe a concrete example would greatly help. Much appreciated
Here’s a teensy bit of code (using OCaml Stdlib Map):
# module SMap = Map.Make(String);;
. . .
# SMap.bindings m3;;
- : (SMap.key * string) list = [("k1", "v1"); ("k2", "v2"); ("k3", "v3")]
# SMap.fold (fun k v res -> res ^ k ^ v) m3 "";;
- : string = "k1v1k2v2k3v3"
The function to be folded over the map has 3 params: the next key, the next value, the accumulated result. It returns a new accumulated result.
I hope this is helpful.
Thank you, so from previous replies and this current one, it seems that the difference between List.fold_right_or_left and Set.S Map Fold is that the building of the list is done automatically for us , and it’s just folding right on this auto generated List. I hope my assumptions are correct, I didn’t fully understand the machinery behind Fold for Map and Set. If anyone else have examples, fell free to share.
The creation of a list from a map is just a good way to think about what Map.fold is doing, especially when getting used to the idea. But in the actual implementation no list is created. If you look at the code you quoted above you can see this. It runs the folded function directly over the internal tree representing the map.
Thank you, I did some research a wizard in the functional programming academic community replied about fold in general " a higher order function for aggregate operations such as reduce a list of ints to their sum" . So in essence , the fold operation is universal while the implementation varies. And thank you for pointing that out. I wholly believe that OCAML might just be the perfect language , and understanding more of OCAML is something I am very excited about. I noticed that there aren’t many blogs on OCAML and data structures and algorithms, anyone have any examples of functional programming in OCAML especially with data structures and algorithms , feel free to share, it would be awesome to see more algorithms and data structures in OCAML.
I think the most well-known one is Chris Okasaki’s Purely Functional Data Structures (you can Google the PDF). It’s using Standard ML for the implementations but since the language is so close to OCaml it should be relatively easy to translate and understand.
Just as compilers target a specific language to emit code, I am trying to target OCAML to learn data structures and algorithms in OCAML. There just isn’t materials out there, maybe we should continue this thread and present the data structures and algos in OCAML. As Linus famously said, think in data structures rather than just code. And, having more resources in algo and data structures in OCAML would help everyone to build OCAML apps. The next app I am building for fun will be a web server, and I am thinking writing it in OCAML and C. I think thats the perfect combo for writing end to end apps.