Traversing graphs

[Thomas Johnsson]

To be precise, this is call-by-name, and not call-by-need (perhaps that 
is what Tony meant by WARNING?) In call-by-name, a shared delay() value 
is evaluated every time its value is needed.
In call-by-need, the same shared value is evaluated at most once: the 
first time its value is needed, the shared delay() is updated with the 
value so that all other usages benefit from that first evaluation.
Would be nice to have some basic mechanism in Erlang so that 
call-by-need could be implemented. It would have to be light weight, 
updateable, and GC-able. Would probably a disaster to let loose on the 
unsuspecting Erlang programming community, though (:-)

The sieve example works nicely because it needs only call-by-name. In 
other cases, complexity can easily become exponential when you'd 
otherwise expect linear time, canonical example here is a tabulated 
fibonacci:

fiblist = [ fib(I) || I <- [0..] ] .
fibt(N) -> nth(fiblist,N).
fib(0) -> 1
fib(1) -> 1
fib(N) -> fibt(N-1)+fibt(N-2).

-- Thomas


Tony Rogvall wrote:

>
> 25 maj 2005 kl. 15.50 skrev Vlad Dumitrescu:
>
>> Hi all,
>>  
>> I just hit a problem where I clearly see how simple it would be with 
>> lazy evaluation. But since we don't have that, I wonder if anyone 
>> could point me to some non-lazy algorithms.
>>  
>
>
> By working a bit, lazy evaluation can be done... (WARNING do not use 
> in real apps ;-)
>
> For example using the macros:
>
> -define(delay(X), fun() -> (X) end).
>
> -define(force(X), force((X))).
>
> force(F) when function(F) -> F();
> force(V) -> V.
>
>
> You can define a lazy algorithms (can of course only be used in this 
> context)
>
> zeros() ->
>     [0 | ?delay(zeros())].
>
> ones() ->
>     [1 | ?delay(ones())].
>
> twos() ->
>     [2 | ?delay(ones())].
>
> seq(Start) ->
>     [Start | ?delay(seq(Start+1))].
>
>
> sieve1(L, P) ->
>     [N | T1] = ?force(L),
>     case N rem P of
>         0 -> sieve1(T1,P);
>         _ -> sieve([N | ?delay(sieve1(T1,P))])
>     end.
>
> sieve(L) ->
>     [P | X] = ?force(L),
>     [P | ?delay(sieve1(X, P))].
>
> primes() ->
>     sieve(seq(2)).
>
> Regards
>
> /Tony
>
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20050525/252fd38e/attachment.htm>