Algorithmic lists

[Ulf Wiger]

On Mon, 16 Oct 2000, Ulf Wiger wrote:

>
>Here's my first (and perhaps last) hack of sys_pre_expand.erl.
>It handles at least my very simple test function with a list
>comprehension that is fed a lazy list:

OK, since noone complained too much, here's a hack of lists.erl,
where most functions have been enhanced to operate on both eager
and lazy lists.

The functions that do not accept lazy lists are:
- append() and subtract(), of course, since they rely on BIFs
  (append() works for some combinations, see below)
- suffix(), since it was difficult to modify slightly without losing
  efficiency
- sort(), merge(), rmerge()
- keymember() and keysearch(), since they are BIFs
- keysort(), keymerge()

I wrote a testsuite called listtest.erl. I've reformatted the output
slightly to make it more readable.

It would be interesting if someone with ready access to estone could 
see if the modified functions are now slower for eager lists.

BTW, with these modifications, list comprehensions in the Erlang shell
also work with lazy lists.

/Uffe

PS I just discovered the ??Arg macro syntax. Great for stuff like a
simple test module. (:

1> listtest:run(concise).
"lists:seq(1, 5)" -> [1,2,3,4,5]
"lists:seq(1, 3)" -> [1,2,3]
"seq(1, 5)" -> [1|#Fun<listtest.0.59150742>]
"seq(1, 2)" -> [1|#Fun<listtest.0.59150742>]
"lists:append(Seq15, Seq15)" -> [1,2,3,4,5,1,2,3,4,5]
"lists:append(Seq15, Lzy15)" ->
[1,2,3,4,5,1|#Fun<listtest.0.59150742>]
"lists:append(Lzy15, Lzy15)" ->{'EXIT',badarg}
"lists:append([Seq15, Seq15])" -> [1,2,3,4,5,1,2,3,4,5]
"lists:append([Seq15, Lzy15])" ->
   [1,2,3,4,5,1|#Fun<listtest.0.59150742>]
"lists:append([Lzy15, Seq15])" ->{'EXIT',badarg}
"lists:reverse(Seq15)" -> [5,4,3,2,1]
"lists:reverse(Lzy15)" ->{'EXIT',badarg}
"lists:nth(3, Seq15)" -> 3
"lists:nth(3, Lzy15)" -> 3
"lists:nthtail(3, Seq15)" -> [4,5]
"lists:nthtail(3, Lzy15)" -> [4|#Fun<listtest.0.59150742>]
"lists:prefix(Seq13, Seq15)" -> true
"lists:prefix(Seq13, Lzy15)" -> true
"lists:prefix(Lzy13, Seq15)" -> true
"lists:prefix(Lzy15, Seq13)" -> false
"lists:prefix(Seq15, Seq13)" -> false
"lists:prefix(Seq15, Lzy13)" -> false
"lists:last(Seq15)" -> 5
"lists:last(Lzy15)" -> 5
"lists:sum(Seq15)" -> 15
"lists:sum(Lzy15)" -> 15
"lists:min(Seq15)" -> 1
"lists:min(Lzy15)" -> 1
"lists:max(Seq15)" -> 5
"lists:max(Lzy15)" -> 5
"lists:sublist(Seq15, 2, 2)" -> [2,3]
"lists:sublist(Lzy15, 2, 2)" -> [2,3]
"lists:delete(3, Seq15)" -> [1,2,4,5]
"lists:delete(3, Lzy15)" -> [1,2,4|#Fun<listtest.0.59150742>]
"lists:flatten([Seq15, [Seq15]])" -> [1,2,3,4,5,1,2,3,4,5]
"lists:flatten([Seq15, [Lzy15]])" -> [1,2,3,4,5,1,2,3,4,5]
"lists:flatten([Lzy15, [Lzy15]])" -> [1,2,3,4,5,1,2,3,4,5]
"lists:flatten([Lzy15, [Seq15]])" -> [1,2,3,4,5,1,2,3,4,5]
"lists:flatlength([Seq15, [Seq15]])" -> 10
"lists:flatlength([Seq15, [Lzy15]])" -> 10
"lists:flatlength([Lzy15, [Lzy15]])" -> 10
"lists:flatlength([Lzy15, [Seq15]])" -> 10
"lists:keydelete(3, 1, [{N, a} || N <- seq(1, 5)])" ->
   [{1,a},{2,a},{4,a},{5,a}]
"lists:keydelete(3, 1, [{N, a} || N <- lists:seq(1, 5)])" ->
  [{1,a},{2,a},{4,a},{5,a}]
"lists:keyreplace(3, 1, [{N, a} || N <- seq(1, 5)], 33)" ->
   [{1,a},{2,a},33,{4,a},{5,a}]
"lists:keyreplace(3, 1, [{N, a} || N <- lists:seq(1, 5)], 33)" ->
   [{1,a},{2,a},33,{4,a},{5,a}]
"lists:keymap(fun(X) -> [X] end, 2, [{N, a} || N <- seq( 1, 5)])" ->
  lists:seq(1, 5)])" -> [{1,[a]},{2,[a]},{3,[a]},{4,[a]},{5,[a]}]
"lists:keymap(fun(X) -> [X] end, 2, [{N, a} || N <-
  lists:seq(1, 5)])" -> [{1,[a]},{2,[a]},{3,[a]},{4,[a]},{5,[a]}]
"lists:all(fun(N) when integer(N) -> true ;(_) -> false end, Seq15)" -> true
"lists:all(fun(N) when integer(N) -> true ;(_) -> false end, Lzy15)" -> true
"lists:all(fun(N) when N > 1, N < 4 -> true ;(_) -> false end, Seq15)" -> false
"lists:all(fun(N) when N > 1, N < 4 -> true ;(_) -> false end, Lzy15)" -> false
"lists:any(fun(N) when N > 1, N < 4 -> true ;(_) -> false end, Seq15)" -> true
"lists:any(fun(N) when N > 1, N < 4 -> true ;(_) -> false end, Lzy15)" -> true
"lists:map(fun(N) -> N + 1 end, Seq15)" -> [2,3,4,5,6]
"lists:map(fun(N) -> N + 1 end, Lzy15)" -> [2,3,4,5,6]
"lists:flatmap(fun(N) -> [N + 1] end, Seq15)" ->
   [2,3,4,5,6]
"lists:flatmap(fun(N) -> [N + 1] end, Lzy15)" ->
   [2,3,4,5,6]
"lists:foldl(fun(N, Acc) -> Acc + 1 end, 0, Seq15)" -> 5
"lists:foldl(fun(N, Acc) -> Acc + 1 end, 0, Lzy15)" -> 5
"lists:zf(fun(N) when N>1,N<4 ->{true,[N]} ;(_)-> false end, Seq15)" ->
   [[2],[3]]
"lists:zf(fun(N) when N>1,N<4 ->{true, [N]} ;(_)-> false end, Lzy15)" ->
   [[2],[3]]
i:1
i:2
i:3
i:4
i:5
"lists:foreach(fun(N) -> io : format(\"i:~p~n\", [N]) end, Seq15)" -> ok
i:1
i:2
i:3
i:4
i:5
i:1
i:2
i:3
i:4
i:5
"lists:foreach(fun(N) -> io:format(\"i:~p~n\",[N]) end, Lzy15)" -> ok
i:1
i:2
i:3
i:4
i:5
"lists:mapfoldl(fun(N, Acc) ->{N + 1, Acc + N} end, 0,Seq15)" ->
  {[2,3,4,5,6],15}
"lists:mapfoldl(fun(N, Acc) ->{N + 1, Acc + N} end, 0,Lzy15)" ->
  {[2,3,4,5,6],15}
"lists:mapfoldr(fun(N, Acc) ->{N + 1, Acc + N} end, 0,Seq15)" ->
  {[2,3,4,5,6],15}
"lists:mapfoldr(fun(N, Acc) ->{N + 1, Acc + N} end, 0,Lzy15)" ->
   {[2,3,4,5,6],15}
"lists:takewhile(fun(N) when N < 3 -> true ;(_) -> false end, Seq15)" ->
   [1,2]
"lists:takewhile(fun(N) when N < 3 -> true ;(_) -> false end, Lzy15)" ->
   [1,2]
"lists:dropwhile(fun(N) when N < 3 -> true ;(_) -> false end, Seq15)" ->
   [3,4,5]
"lists:dropwhile(fun(N) when N < 3 -> true ;(_) -> false end, Lzy15)" ->
   [3|#Fun<listtest.0.59150742>]
"lists:splitwith(fun(N) when N < 3 -> true ;(_) -> false end, Seq15)" ->
{[1,2],[3,4,5]}
"lists:splitwith(fun(N) when N < 3 -> true ;(_) -> false end, Lzy15)" ->
{[1,2],[3|#Fun<listtest.0.59150742>]}


-- 
Ulf Wiger                                    tfn: +46  8 719 81 95
Strategic Product & System Management        mob: +46 70 519 81 95
Ericsson Telecom AB,              Datacom Networks and IP Services
Varuvägen 9, Älvsjö,                    S-126 25 Stockholm, Sweden
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lazy.tgz
Type: application/octet-stream
Size: 14014 bytes
Desc: lazy.tgz
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20001017/aa81430f/attachment.obj>