Position of anonymous function’s parameters in SML’s foldl

user_16420024 0
Viewed 79

I need to write a function that takes a list of strings and finds the largest string in the list. In case of tie, it should return string closest to the end of the list. The catch is it needs to iterate through the list using List.foldl and cannot use recursive calls except for those in the library function of List,foldl. The following code works fine.

fun longest_string2 str_list =
     List.foldl(fn (x, acc) => if String.size x >= String.size acc then x else acc) "” str_list

If I run longest_string2 ["Apple", "ball", "Bpple”]; in REPL, I get val it = "Bpple" : string However, if I reverse the arguments of anonymous function as below I get val it = "Apple" : string. Since the anonymous function is accessing the elements by name and not position, why does this makes difference?

sml
2 Answers

The definition of List.foldl is

fun foldl (f: 'a*'b->'b) (acc: 'b) (l: 'a list): 'b =
  case l of
    [] => acc
  | x::xs => foldl f (f(x,acc)) xs

If you reverse arguments of the anonymous function, your function becomes the following: (correct me if I misinterpreted your question)

fun longest_string2 str_list =
     List.foldl(fn (acc, x) => if String.size x >= String.size acc then x else acc) "” str_list

If your pass ["Apple", "ball", "Bpple”] as argument to longest_string2 now, the foldl function will pattern match your list with x::xs, where x is “Apple” and xs is ["ball", "Bpple”]. When you compute the updated accumulator using f(x, acc), x and acc gets swapped. In other words, in your anonymous function (with reversed arguments), you would be assuming that the first argument would be ”” and the second argument would be Apple but the implementation of List.foldl will pass f(“Apple”, “”). In this case, your anonymous function will label “Apple” as “acc” and “” as “x”.

user_108471840

@3123 has most answered the question, but has not directly addressed this statement in the question.

Since the anonymous function is accessing the elements by name and not position, why does this makes difference?

foldl takes a function which takes a tuple as its argument, which is positional.

We could define a fold function which takes a record as its argument instead if we really wanted to achieve this:

fun namedFold _ acc [] = acc
  | namedFold f acc (x::xs) =
      namedFold f (f {acc=acc, x=x}) xs;

And then call it as:

namedFold (fn { acc, x } => acc + x) 0 [1,2,3,4]

Or as:

namedFold (fn { x, acc } => acc + x) 0 [1,2,3,4]

And get the same result.

But then the type of namedFold is fn :({acc: 'a, x: 'b} -> 'a) -> 'a -> 'b list -> 'a and it becomes essentially impossible to easily pass existing functions to it. With foldl defined the way it is, we can easily rewrite that previous called to namedFold as:

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

Because op+ has the same signature as the first argument to foldl.

user_152613150
Related