Erlang: is it possible to write the minimum function as a list fold?

Question

Given a function:

min(A, B)  when A =< B -> A;
min(_A, B)             -> B.

can I use this in the function foldlin a similar fashion to this:

lists:foldl(fun min/2, 0, [1,2,3,4,5,6,7,8,9,10])

I believe it is not possible, because I have to set an initial value that will be compared to the rest of the list, e. g. there is no identity function that I can think of. Am I right?

Syntax is written in Erlang, but should be readable for non Erlang programmers, too.

I guess I could, and that would crash on empty list as pointed out below. — Magnus Kronqvist, Mar 02 '11 at 13:54
Yasir's and Adam's answers are both good, crashing on empty list can and can't be acceptable depending on the context. BTW fixed your example so it is possible to compile it. — Peer Stritzinger, Mar 02 '11 at 14:08
Thanks, @Peer. Also, I think that `undefined` wouldn't make quite a lot of sense, see, for example, ["Best explanation for Languages without Null"](http://stackoverflow.com/q/3989264/298282). — YasirA, Mar 02 '11 at 14:13

Adam Lindberg · Answer 1 · 2011-03-02T14:42:27.747

11

min(List) ->
    Min = fun(A,  B) when A < B -> A;
             (_A, B)            -> B end,
    lists:foldl(Min, undefined, List).

Using undefined as the initial state should do the trick. Returns undefined for an empty list, which is kind of nice as an API.

If you want it to crash on an empty list, use this function header instead:

min([Head|Rest]) ->
    Min = fun(A,  B) when A < B -> A;
             (_A, B)            -> B end,
    lists:foldl(Min, Head, Rest).

edited Mar 02 '11 at 14:42

answered Mar 02 '11 at 13:43

Adam Lindberg

16,447
6
65
85

Good answer! Seems even like the first guard (undefined,B) -> B is redundant. – Magnus Kronqvist Mar 02 '11 at 13:52
Actually just out randomness it does not crash. I don't know if the result is deterministic, but out of the examples I have tried with, a comparison of any number and atom returns the number as being smaller. – Magnus Kronqvist Mar 02 '11 at 14:03
3

Passing `undefined` works because there is a well-defined order for the `<` operator when working with heterogenous types. In particular, Numbers are always less than atoms. Look up the order functions in the reference manual. – I GIVE CRAP ANSWERS Mar 02 '11 at 16:10

score 5 · Accepted Answer · edited Mar 02 '11 at 14:00

5

1> List = [42,13,25,3,19,20].
[42,13,25,3,19,20]
2> lists:foldl(fun(X, Y) -> erlang:min(X,Y) end, hd(List), tl(List)).   
3

Crashes a program on an empty list, a recommended approach "let it crash" as opposed to defensive programming.

edited Mar 02 '11 at 14:00

Peer Stritzinger

8,232
2
30
43

answered Mar 02 '11 at 13:46

YasirA

9,531
2
40
61

Oops, the last argument to the `foldl` should be `tl(List)` (the list tail). I wish we had the function `foldl1` which is found in Haskell, so that we don't use the initial value. – YasirA Mar 02 '11 at 13:55

score 2 · Answer 3 · answered Mar 04 '11 at 15:20

Adam Lindbergs proposal to use undefined as initial value has the disadvantage that it generates weird results for lists that has atoms as members. Erlang has a global ordering of all objects, so a nice property of a min function would be to be usable for all types.

I think its more reasonable to crash on an empty list. The difference is that the client has to worry about the case, instead of having to worry about getting a undefined as the result.

Erlang: is it possible to write the minimum function as a list fold?

3 Answers3