SML Syntax Breakdown

Question

I am trying to study SML (for full transparency this is in preparation for an exam (exam has not started)) and one area that I have been struggling with is higher level functions such as map and foldl/r. I understand that they are used in situations where you would use a for loop in oop languages (I think). What I am struggling with though is what each part in a fold or map function is doing. Here are some examples that if someone could break them down I would be very appreciative

fun cubiclist L = map (fn x=> x*x*x) L;

fun min (x::xs) = foldr (fn (a,b) => if (a < b) then a else b) x xs;

So if I could break down the parts I see and high light the parts I'm struggling with I believe that would be helpful.

Obviously right off the bat you have the name of the functions and the parameters that are being passed in but one question I have on that part is why are we just passing in a variable to cubiclist but for min we pass in (x::xs)? Is it because the map function is automatically applying the function to each part in the map? Also along with that will the fold functions typically take the x::xs parameters while map will just take a variable?

Then we have the higher order function along with the anonymous functions with the logic/operations that we want to apply to each element in the list. But the parameters being passed in for the foldr anonymous function I'm not quite sure about. I understand we are trying to capture the lowest element in the list and the then a else b is returning either a or b to be compared with the other elements in the list. I'm pretty sure that they are rutnred and treated as a in future comparisons but where do we get the following b's from? Where do we say b is the next element in the list?

Then the part that I really don't understand and have no clue is the L; and x xs; at the end of the respective functions. Why are they there? What are they doing? what is their purpose? is it just syntax or is there actually a purpose for them being there, not saying that syntax isn't a purpose or a valid reason, but does they actually do something? Are those variables that can be changed out with something else that would provide a different answer?

Any help/explanation is much appreciated.

Answer 1

In addition to what @molbdnilo has already stated, it can be helpful to a newcomer to functional programming to think about what we're actually doing when we crate a loop: we're specifying a piece of code to run repeatedly. We need an initial state, a condition for the loop to terminate, and an update between each iteration.

Let's look at simple implementation of map.

fun map f [] = []
  | map f (x :: xs) = f x :: map f xs

• The initial state of the contents of the list.
• The termination condition is the list is empty.
• The update is that we tack f x onto the front of the result of mapping f to the rest of the list.

The usefulness of map is that we abstract away f. It can be anything, and we don't have to worry about writing the loop boilerplate.

Fold functions are both more complex and more instructive when comparing to loops in procedural languages.

A simple implementation of fold.

fun foldl f init [] = init
  | foldl f init (x :: xs) = foldl f (f init x) xs

• We explicitly provide an initial value, and a list to operate on.
• The termination condition is the list being empty. If it is, we return the initial value provided.
• The update is to call the function again. This time the initial value is updated, and the list is the tail of the original.

Consider summing a list of integers.

foldl op+ 0 [1,2,3,4]
foldl op+ 1 [2,3,4]
foldl op+ 3 [3,4]
foldl op+ 6 [4]
foldl op+ 10 []
10

Folds are important to understand because so many fundamental functions can be implemented in terms of foldl or foldr. Think of folding as a means of reducing (many programming languages refer to these functions as "reduce") a list to another value of some type.

Answer 2

map takes a function and a list and produces a new list.

In map (fn x=> x*x*x) L, the function is fn x=> x*x*x, and L is the list.
This list is the same list as cubiclist's parameter.

foldr takes a function, an initial value, and a list and produces some kind of value.

In foldr (fn (a,b) => if (a < b) then a else b) x xs, the function is fn (a,b) => if (a < b) then a else b, the initial value is x, and the list is xs.
x and xs are given to the function by pattern-matching; x is the argument's head and xs is its tail.
(It follows from this that min will fail if it is given an empty list.)