lazy.erl

-module(lazy).
-compile(export_all).
-include_lib("eunit/include/eunit.hrl").

%% A lazy list is build from cells containing the value of their current
%% computation and a function that will return the next one.
%% Once a lazy list is over, the atom 'done' is returned.
-define(lcell(Term, Fun), {Term, Fun}).
-type lcell() :: {term(), fun(() ->  tuple() | 'done' )}
               | 'done'.

%% eval takes a lazy list and returns a normal list.
%% Using an infinite list means it goes into an infinite loop.
-spec eval(lcell()) -> list().
eval(done) -> [];
eval(Cell) -> lists:reverse(eval(Cell, [])).

-spec eval(lcell(), list()) -> list().
eval(done, Acc)       -> Acc;
eval(?lcell(Term, Fn), Acc) -> eval(Fn(),[Term|Acc]).

%% convert/1 takes a list and returns a lazy one to be evaluated with
%% functions from this module.
-spec convert(list()) -> lcell().
convert([])    -> done;
convert([H|T]) -> ?lcell(H,fun() -> convert(T) end).

conversion_test() ->
    ?assertEqual([1,2,3],  eval(convert([1,2,3]))).

%%% Functions that do a final evaluation (ie.: return a single element).
%%% They do not require the use of 'eval' in order to work, but can't be
%%% coupled with other functions from this module.

%% all takes a function Pred and applies it to a lazy list. If the Pred
%% returns 'false' once, all/2 also returns false. Otherwise, it returns
%% 'true'.
-spec all(fun((any()) -> boolean()), lcell()) -> boolean().
all(Pred, done) when is_function(Pred) ->
    true;
all(Pred, ?lcell(Term,Fn)) when is_function(Pred) ->
    case Pred(Term) of
        true  -> all(Pred, Fn());
        false -> false
    end.

all_test_() ->
    Pred = fun(X) -> X > 10 end,
    [?_assertEqual(true, all(Pred,seq(11,20))),
     ?_assertEqual(false, all(Pred,seq(9,20))),
     ?_assertEqual(lists:all(Pred,[]), all(Pred, convert([])))].

%% any takes a function Pred and applies it to a lazy list. If the Pred
%% returns 'true' once, any/2 also returns true. Otherwise (all false), 
%% it returns 'false'.
%% -spec any(fun(any()) -> boolean()), lcell()) -> boolean().
%% ^ that spec won't work because the function name clashes with the
%%   dialyzer default 'any()' type.
any(Pred, done) when is_function(Pred) ->
    false;
any(Pred, ?lcell(Term,Fn)) when is_function(Pred) ->
    case Pred(Term) of
        true -> true;
        false -> any(Pred, Fn())
    end.

any_test_() ->
    Pred = fun(X) -> X > 10 end,
    [?_assertEqual(true, any(Pred,seq(11,20))),
     ?_assertEqual(true, any(Pred,seq(9,20))),
     ?_assertEqual(false, any(Pred,seq(1,3))),
     ?_assertEqual(lists:any(Pred,[]), any(Pred, convert([])))].

%% fold will reduce a list from left to right like lists:foldl/3 would.
-spec fold(fun((any(),any()) -> any()), any(), lcell()) -> any().
fold(_, Start, done) -> Start;
fold(F, Start, ?lcell(Term,Fn)) when is_function(F) ->
    fold(F, F(Term,Start), Fn()).

fold_test_() ->
    F = fun(X,Y) -> X*Y end,
    [?_assertEqual(lists:foldl(F,1,lists:seq(1,100)),
                   fold(F,1,seq(1,100))),
     ?_assertEqual(lists:foldl(F,0,[1,2,3,4]), fold(F,0,seq(1,4))),
     ?_assertEqual(24, fold(F,1,seq(1,4)))].

%% member returns 'true' if the element Elem is part of the lazy list and
%% 'false' if it's not. lists:member uses strict comparison (=:=) and so
%% does this one.
-spec member(any(),lcell()) -> boolean().
member(_,done) ->
    false;
member(Elem, ?lcell(Term,Fn)) ->
    if Elem =:= Term -> true;
       true -> member(Elem, Fn())
    end.

member_test_() ->
    [?_assertEqual(true, member(1, seq(1,3))),
     ?_assertEqual(false, member(1, seq(2,3))),
     ?_assertEqual(lists:member(2.0,[1,2,3]), member(2.0,seq(1,3))),
     ?_assertEqual(lists:member(2.0,[1.0,2.0,3.0]),
                   member(2.0,convert([1.0,2.0,3.0])))].

%% nth takes a lazy cell and will return the nth result from there.
%% the function is 1-indexed in order to be coherent with the rest of
%% Erlang.
-spec nth(non_neg_integer(), lcell()) -> any().
nth(_,done)     -> [];
nth(1,?lcell(Term,_)) -> Term;
nth(N,?lcell(_,Fn))   -> nth(N-1, Fn()).

nth_test_() ->
    [?_assertEqual(2, nth(4,convert([3,7,9,2,6,3]))),
     ?_assertEqual(2, nth(4,convert([3,7,9,2]))),
     ?_assertEqual([], nth(4,convert([])))].
%%% These functions can be combined together.

%% seq is the equivalent to lists:seq, with lazy cells
-spec seq(integer(), integer()) -> lcell().
seq(From, To) -> seq(From,To,1).

%% same as seq/2, with a step mentioned
-spec seq(integer(), integer(), integer()) -> lcell().
seq(From, To, Step) when is_integer(From), is_integer(To), is_integer(Step),
                         From < To, Step > 0 ->
    ?lcell(From, fun() -> seq(From+Step, To, Step) end);
seq(From, To, Step) when is_integer(From), is_integer(To), is_integer(Step),
                         To < From, Step < 0 ->
    ?lcell(From, fun() -> seq(From+Step, To, Step) end);
seq(From, To, Step) when is_integer(From), is_integer(To), is_integer(Step),
                         To == From ->
    ?lcell(From, fun() -> done end);
seq(From, To, Step) when is_integer(From), is_integer(To), is_integer(Step),
                         Step < 0, From =< To ->
    done;
seq(From, To, Step) when is_integer(From), is_integer(To), is_integer(Step),
                         Step > 0, From >= To ->
    done.

seq_test_() ->
    [?_assertEqual([1,2,3,4], eval(seq(1,4))),
     ?_assertEqual([4,3,2,1], eval(seq(4,1,-1))),
     ?_assertEqual("ABCD", eval(seq($A,$D))),
     ?_assertEqual(lists:seq(40,230,12), eval(seq(40,230,12))),
     ?_assertEqual(lists:seq(1,10,2), eval(seq(1,10,2)))].

%% sublist is exactly similar to lists:sublist, except in a lazy version
%% which needs to be evaluated by eval/1. Note that in the case of
%% sublist/2 and sublist/3, the List actually comes as the first argument:
%% this is done to be consistent with the lists module function.
-spec sublist(lcell(), non_neg_integer()) -> lcell().
sublist(Cell, Len) -> sublist(Cell, 1, Len).

-spec sublist(lcell(), non_neg_integer(), non_neg_integer()) -> lcell().
sublist(done, Start, Len) when is_integer(Start), is_integer(Len) ->
    done;
sublist(?lcell(Term,_Fn), 1, 1) ->
    ?lcell(Term, fun() -> done end);
sublist(?lcell(Term, Fn), 1, Len) when is_integer(Len) ->
    ?lcell(Term, fun() -> sublist(Fn(), 1, Len-1) end);
sublist(?lcell(_, Fn), Start, Len) when is_integer(Start), is_integer(Len) ->
    sublist(Fn(), Start-1, Len).

sublist_test_() ->
    [?_assertEqual(lists:sublist([1,2,3,4],3), eval(sublist(seq(1,4),3))),
     ?_assertEqual(lists:sublist([1,2,3],4), eval(sublist(seq(1,3),4))),
     ?_assertEqual(lists:sublist([1,2,3,4,5],3,4),
                   eval(sublist(seq(1,5),3,4))),
     ?_assertEqual(lists:sublist(lists:seq(1,3),9),
                   eval(sublist(seq(1,3),9))),
     ?_assertEqual(lists:sublist([1,2,3,4,5,6],3,2),
                   eval(sublist(seq(1,6),3,2)))].


%% map applies a function to each element of a list, returning a list.
-spec map(fun(), lcell()) -> lcell().
map(F,done) when is_function(F) ->
    done;
map(F,?lcell(Term,Fn)) when is_function(F) ->
    ?lcell(F(Term), fun() -> map(F, Fn()) end).

map_test_() ->
    F = fun(X) -> X*2 end,
    [?_assertEqual(lists:map(F,[1,2,3,4,5]), eval(map(F,seq(1,5)))),
     ?_assertEqual(lists:map(F,[]), eval(map(F,convert([]))))].

%% filter returns only elements of the lazy list which return true when
%% passed to Pred
-spec filter(fun((any()) -> boolean()), lcell()) -> lcell().
filter(_,done) -> done;
filter(F,?lcell(Term, Fn)) when is_function(F) ->
    case F(Term) of
        true -> ?lcell(Term, fun() -> filter(F, Fn()) end);
        false -> filter(F,Fn())
    end.

filter_test_() ->
    F = fun(X) -> X rem 2 =:= 0 end,
    [?_assertEqual(lists:filter(F,lists:seq(1,100)),
                   eval(filter(F,seq(1,100)))),
     ?_assertEqual(lists:filter(F,[]), eval(filter(F,convert([]))))].

%% append/2 takes two lists and appends the second one to the first one.
-spec append(lcell(),lcell()) -> lcell().
append(done,done) -> done;
append(done,?lcell(Term,Fn)) ->
    ?lcell(Term, fun() -> append(done, Fn()) end);
append(?lcell(Term,Fn),Cell) ->
    ?lcell(Term, fun() -> append(Fn(),Cell) end).

append_test_() ->
    [?_assertEqual(lists:append([1,2,3],[4,5,6]),
                   eval(append(seq(1,3),seq(4,6)))),
     ?_assertEqual(lists:append([],[]),
                   eval(append(convert([]),convert([])))),
     ?_assertEqual(lists:append([],[1,2,3]), 
                   eval(append(convert([]),seq(1,3)))),
     ?_assertEqual(lists:append([1,2,3],[]),
                   eval(append(seq(1,3),convert([]))))].


%% takewhile keeps building the list until the predicate returns false.
-spec takewhile(fun((any()) -> boolean()), lcell()) -> lcell().
takewhile(Pred, done) when is_function(Pred) -> done;
takewhile(Pred, ?lcell(Term, Fn)) when is_function(Pred) ->
    case Pred(Term) of
        true -> ?lcell(Term, fun() -> takewhile(Pred,Fn()) end);
        false -> done
    end.

takewhile_test_() ->
    Pred = fun(X) -> X < 5 end,
    [?_assertEqual(lists:takewhile(Pred, lists:seq(1,10)),
                   eval(takewhile(Pred, seq(1,10)))),
     ?_assertEqual(lists:takewhile(Pred, lists:seq(10,15)),
                   eval(takewhile(Pred, seq(10,15))))].

%% dropwhile keeps ignoring elements of a list until the predicate returns
%% true. It's technically not lazy and will do all the computations at once
%% but the list returned after will be.
-spec dropwhile(fun((any()) -> boolean()), lcell()) -> lcell().
dropwhile(Pred, done) when is_function(Pred) -> done;
dropwhile(Pred, ?lcell(Term, Fn)) when is_function(Pred) ->
    case Pred(Term) of
        true -> dropwhile(Pred, Fn());
        false -> ?lcell(Term, fun() -> dropwhile(Pred,Fn()) end)
    end.

dropwhile_test_() ->
    Pred = fun(X) -> X < 5 end,
    [?_assertEqual(lists:dropwhile(Pred, lists:seq(1,10)),
                   eval(dropwhile(Pred, seq(1,10)))),
     ?_assertEqual(lists:dropwhile(Pred, lists:seq(1,3)),
                   eval(dropwhile(Pred, seq(1,3))))].

%% zip/2 takes two lists Xs and Ys and makes a list of tuples of the form
%% [{Xn,Yn}]. The implementation differs from the standard lists one as
%% the lists one fails if the count of list elements is differnet in the
%% first and second one. This one just stops whenever one of the lists is
%% over.
-spec zip(lcell(), lcell()) -> lcell().
zip(done,_) -> done;
zip(_,done) -> done;
zip(?lcell(TermX,FnX), ?lcell(TermY,FnY)) ->
    ?lcell({TermX,TermY}, fun() -> zip(FnX(),FnY()) end).

zip_test_() ->
    [?_assertEqual([{1,5},{2,6},{3,7},{4,8}], eval(zip(seq(1,4),seq(5,8)))),
     ?_assertEqual([{1,10},{2,11}], eval(zip(seq(1,2),seq(10,1000)))),
     ?_assertEqual([], eval(zip(convert([]),seq(1,1000))))].

%% zipwith/3 takes a function and two lists Xs and Ys and combines them
%% using the function.
%% As an example, if the combining function is fun(X,Y) -> {X,Y} end, the
%% zipwith function behaves exactly as zip/2. A different behavior could be
%% demonstrated with the combining function fun(X,Y) -> X+Y end, which,
%% coupled with the lists [1,2,3] and [4,5,6,7] would give [5,7,9].
-spec zipwith(fun( (any(),any()) -> any() ), lcell(), lcell()) -> lcell().
zipwith(F,done,_) when is_function(F) -> done;
zipwith(F,_,done) when is_function(F) -> done;
zipwith(F, ?lcell(TermX, FnX), ?lcell(TermY, FnY)) when is_function(F) ->
    ?lcell(F(TermX, TermY), fun() -> zipwith(F, FnX(), FnY()) end).

zipwith_test_() ->
    Fn = fun(X,Y) -> {X, Y} end,
    [?_assertEqual(eval(zip(seq(1,4), seq(5,8))),
                   eval(zipwith(Fn, seq(1,4), seq(5,8)))),
     ?_assertEqual(eval(zip(seq(1,3), seq(1,1000))),
                   eval(zipwith(Fn, seq(1,3), seq(1,1000)))),
     ?_assertEqual([2,4,6,8],
                   eval(zipwith(fun(X,Y) -> X+Y end, seq(1,4), seq(1,10))))].
%% builder lets you use a function to produce the next element your lazy
%% list will contain, may it be from a stream or even raw input from the
%% shell.
%%
%% It will however be slower than other functions because of its need to
%% do checks through a function rather than pattern match.
-spec builder(any(), fun((any()) -> boolean()), fun()) -> lcell().
builder(Term, Stop, Step) ->
    case Stop(Term) of
        true -> done;
        false -> ?lcell(Term, fun() -> builder(Step(Term), Stop, Step) end)
    end.

builder_test_() ->
    [?_assertEqual(lists:seq(1,100,4),
                   eval(builder(1,fun(X)-> X>=100 end, fun(X) -> X+4 end)))].