Traversing graphs
Thomas Johnsson
<>
Wed May 25 22:12:29 CEST 2005
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.html>
More information about the erlang-questions
mailing list