SML/NJ - One line length function using foldr

Question

I'm trying to create a length function, similar to the one already included in ML. My restrictions are that it has to be done on one line and use either map, foldl, or foldr.

Right now my line of code looks like this:

val mylength = foldr ( fn(x,y) => 1+y) 0;

I am by no means an expert at ML, but my reasoning so far is this:

To my understanding, foldr will, beginning at the last item in the list, pass it as the x argument in my function and use the 0 as the initial y value. It should then add 1 to the y value and basically ignore x. In theory, I believed this would give me my total length. However I am given the following error:

 stdIn:136.5-136.37 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
 val mylength = fn : ?.X1 list -> int

My big problem is figuring out how to create this function in a way that it can accept lists of any type.

If anyone could offer some advice about how to approach this problem I would appreciate it, perhaps I still haven't wrapped my head around ML's style of programming.

Answer 1

Your function is correct in essence. Depending on what interpreter you use, it will accept the given code or reject it. For instance, running your code on CloudML will do just fine. To avoid this problem rather define it as a function like this:

fun mylength l = foldr ( fn(x,y) => 1+y) 0 l;

Daniel Grossman from the University of Washington explained in one of his lessons that this error has to do with mutable references. Regretfully, I can't recall exactly in which lesson he mentioned this.

You may consider the following in the meanwhile:

• SML Warning: Type Vars Not Generalized when using Empty Lists or NONE option
• Polymorphic function as return value and value restriction in SML
• The value restriction

Answer 2

Given some standard definitions for foldl and foldr:

fun foldr f e []      = e
  | foldr f e (x::xr) = f(x, foldr f e xr);

fun foldl f e []      = e
  | foldl f e (x::xr) = foldl f (f(x, e)) xr;

One can manually apply your function to a short list and see how term rewriting unfolds:

foldr (fn(_,y) => 1+y) 0 [5,6,7]
(fn(_,y) => 1+y) (5,foldr (fn(_,y) => 1+y) 0 [6,7])
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,foldr (fn(_,y) => 1+y) 0 [7]))
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,(fn(_,y) => 1+y) (7,foldr (fn(_,y) => 1+y) 0 [])))
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,(fn(_,y) => 1+y) (7,0)))
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,1))
(fn(_,y) => 1+y) (5,2)
3

With foldr you can see that the the element 7 is resolved first (it folds from right to left) and that the length of the expression (and thus the stack memory) grows proportionally to the list. With foldl you can see that 5 is resolved first (it folds from left to right) and that the length of the expression is constant. In both cases the first part of the argument to the anonymous function is discarded.

foldl (fn(_,y) => 1+y) 0 [5,6,7]
foldl (fn(_,y) => 1+y) ((fn(_,y) => 1+y)(5, 0)) [6,7]
foldl (fn(_,y) => 1+y) 1 [6,7]
foldl (fn(_,y) => 1+y) ((fn(_,y) => 1+y)(6, 1)) [7]
foldl (fn(_,y) => 1+y) 2 [7]
foldl (fn(_,y) => 1+y) ((fn(_,y) => 1+y)(7, 2)) []
foldl (fn(_,y) => 1+y) 3 []
3

Admittedly, the lambdas clutter up the whole thing. Given the definition

fun plus1(_,y) = 1+y

The following rewriting is equivalent but more legible.

foldr plus1 0 [5,6,7]
plus1 (5, foldr plus1 0 [6,7])
plus1 (5, plus1 (6, foldr plus1 0 [7]))
plus1 (5, plus1 (6, plus1 (7, foldr plus1 0 [])))
plus1 (5, plus1 (6, plus1 (7, 0)))
plus1 (5, plus1 (6, 1))
plus1 (5, 2)
3

foldl plus1 0 [5,6,7]
foldl plus1 (plus1 (5,0)) [6,7]
foldl plus1 1 [6,7]
foldl plus1 (plus1 (6,1)) [7]
foldl plus1 2 [7]
foldl plus1 (plus1 (7,2)) []
foldl plus1 3 []
3

Answer 3

A slightly longer solution (which I came up with by trying to think how map could be relevant):

fun len xs = (foldr op+ 0 o map (fn x => 1)) xs;

Here o is the composition operator. I wanted to write

val len  = foldr op+ 0 o map (fn x => 1); 

so as to mimic the sort of point-free style popular in Haskell but ran into exactly the same value restriction that your original definition encountered.