SML / NJ - one line length function using foldr

Question

I am trying to create a length function similar to the one already included in ML. My limitations are that this needs to be done on the same line and use either a card, 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 in ML, but so far I have reasoned as follows:

As far as I understand, foldr will, starting from the last element in the list, pass it as an argument x in my function and use the value 0 as the initial value of y. Then it should add 1 to the y value and basically ignore x. In theory, I thought this would give me my total length. However, I get 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 how to create this function so that it can accept lists of any type.

If anyone could offer some advice on how to approach this problem, I would appreciate it, maybe I still haven't wrapped myself in ML programming style.

Answer 1

Your function is essentially true. Depending on which interpreter you are using, it will accept the given code or reject it. For example, running your CloudML code would be great. To avoid this problem, rather define it as a function:

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

, . , , .

:

• SML: Vars NONE
• SML

Answer 2

foldl 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;

, :

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

foldr , 7 ( ) (, , ) . foldl , 5 ( ) . .

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

, .

fun plus1(_,y) = 1+y

, .

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

( , , map ):

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

o - .

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

to mimic the type of nonsense style popular in Haskell, but faced with the same value constraint that your original definition faced.