[m-dev.] Laziness modules
Ralph Becket
rafe at csse.unimelb.edu.au
Tue May 5 17:04:53 AEST 2009
I put a couple of modules providing support for lazy computation
together at the weekend. Is there any interest in adding these to the
library? Laziness gives us what in the C# and Java worlds they call
"enumerables" and are using to good effect.
-- Ralph
%-----------------------------------------------------------------------------%
% lazy.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Fri Apr 17 15:50:59 EST 2009
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
% Basic lazy evaluation support.
%
%-----------------------------------------------------------------------------%
:- module lazy.
:- interface.
% The type of suspended computations.
%
:- type lazy(T).
% Construct a suspension which will be evaulated at most once.
%
:- func susp((func) = T) = lazy(T).
% Convert a constant into a lazy value.
%
:- func lazy(T) = lazy(T).
% Extract the value of a lazy(T).
%
:- func value(lazy(T)) = T.
%-----------------------------------------------------------------------------%
:- implementation.
% It should be possible to merge the lazyrep with the C representation to
% avoid the need for two allocations per lazy construction, but passing
% higher order functions (like apply/N) to C is so painful that I stuck
% with the more obvious solution.
:- pragma foreign_type("C", lazy(T), "MR_Word *", [can_pass_as_mercury_type]).
:- type lazyrep(T)
---> unevaluated((func) = T)
; evaluated(T).
:- impure pred new_lazy(lazy(T)::out) is det.
:- pragma foreign_proc("C", new_lazy(L::out),
[will_not_call_mercury],
"
L = (MR_Word *)MR_GC_NEW(MR_Word *);
").
:- semipure pred get_lazyrep(lazy(T)::in, lazyrep(T)::out) is det.
:- pragma foreign_proc("C", get_lazyrep(L::in, R::out),
[promise_semipure, will_not_call_mercury],
"
R = *L;
").
:- impure pred set_lazyrep(lazy(T)::in, lazyrep(T)::in) is det.
:- pragma foreign_proc("C", set_lazyrep(L::in, R::in),
[will_not_call_mercury],
"
*L = R;
").
%-----------------------------------------------------------------------------%
susp(S) = L :-
promise_pure (
impure new_lazy(L),
impure set_lazyrep(L, unevaluated(S))
).
%-----------------------------------------------------------------------------%
value(L) = X :-
promise_pure (
semipure get_lazyrep(L, R),
(
R = unevaluated(S),
X = apply(S),
impure set_lazyrep(L, evaluated(X))
;
R = evaluated(X)
)
).
%-----------------------------------------------------------------------------%
lazy(X) = L :-
promise_pure (
impure new_lazy(L),
impure set_lazyrep(L, evaluated(X))
).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
% lazy_list.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Fri Apr 17 15:50:59 EST 2009
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
% Simple lazy list evaluation.
%
%-----------------------------------------------------------------------------%
:- module lazy_list.
:- interface.
:- import_module int.
:- import_module lazy.
:- import_module list.
% The type of lazy lists.
%
:- type lazy_list(T)
---> empty_lazy_list
; lazy_list(T, lazy(lazy_list(T))).
% The lazy list constructor.
%
:- func cons(T, (func) = lazy_list(T)) = lazy_list(T).
% The lazy list deconstructor.
%
:- pred decons(lazy_list(T)::in, T::out, lazy_list(T)::out) is semidet.
% Convert between ordinary lists and lazy lists.
%
:- func list_to_lazy_list(list(T)) = lazy_list(T).
:- func lazy_list_to_list(lazy_list(T)) = list(T).
% Append, map, filter, fold, take, drop for lazy lists.
%
:- func lazy_list(T) ++ lazy_list(T) = lazy_list(T).
:- func map(func(T1) = T2, lazy_list(T1)) = lazy_list(T2).
:- func filter(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
(lazy_list(T)::out) is det.
:- func filter_out(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
(lazy_list(T)::out) is det.
:- func foldl(func(T1, T2) = T2, lazy_list(T1), T2) = T2.
:- func foldr(func(T1, T2) = T2, lazy_list(T1), T2) = T2.
:- func foldr_lazy(func(T1, lazy(T2)) = T2, lazy_list(T1), T2) = T2.
% take(N, Xs) is the first N items of Xs or Xs itself if it has
% fewer than N items.
%
:- func take(int, lazy_list(T)) = lazy_list(T).
% drop(N, Xs) is the remainder of Xs after the first N items have
% been removed or the empty list if Xs has fewer than N items.
%
:- func drop(int, lazy_list(T)) = lazy_list(T).
% The following take or drop elements of a lazy_list while/until
% an item satisfying some condition is found.
%
:- func take_while(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
(lazy_list(T)::out) is det.
:- func drop_while(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
(lazy_list(T)::out) is det.
:- func take_until(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
(lazy_list(T)::out) is det.
:- func drop_until(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
(lazy_list(T)::out) is det.
% Lazy integer sequences.
% ints(Lo, Hi) is the lazy_list [Lo, Lo + 1, ..., Hi].
%
:- func ints(int, int) = lazy_list(int).
% ints(Lo, Hi, Step) is the lazy_list [Lo, Lo + Step, ..., Max]
% where Max is the largest integer <= Hi.
%
:- func ints_with_step(int, int, int) = lazy_list(int).
% ints_from(Lo) is the lazy_list [Lo, Lo + 1, ...].
%
:- func ints_from(int) = lazy_list(int).
% ints_from_with_step(Lo, Step) is the lazy_list [Lo, Lo + Step, ...].
%
:- func ints_from_with_step(int, int) = lazy_list(int).
%-----------------------------------------------------------------------------%
:- implementation.
%-----------------------------------------------------------------------------%
cons(X, Susp) = lazy_list(X, susp(Susp)).
%-----------------------------------------------------------------------------%
decons(lazy_list(X, LLXs), X, value(LLXs)).
%-----------------------------------------------------------------------------%
list_to_lazy_list([]) = empty_lazy_list.
list_to_lazy_list([X | Xs]) =
lazy_list(X, susp((func) = list_to_lazy_list(Xs))).
%-----------------------------------------------------------------------------%
lazy_list_to_list(empty_lazy_list) = [].
lazy_list_to_list(lazy_list(X, LXs)) = [X | lazy_list_to_list(value(LXs))].
%-----------------------------------------------------------------------------%
empty_lazy_list ++ Ys = Ys.
lazy_list(X, LXs) ++ Ys = cons(X, (func) = value(LXs) ++ Ys).
%-----------------------------------------------------------------------------%
map(_, empty_lazy_list) = empty_lazy_list.
map(F, lazy_list(X, LXs)) = cons(F(X), (func) = map(F, value(LXs))).
%-----------------------------------------------------------------------------%
filter(_, empty_lazy_list) = empty_lazy_list.
filter(P, lazy_list(X, LXs)) =
( if P(X) then
cons(X, (func) = filter(P, value(LXs)))
else
filter(P, value(LXs))
).
%-----------------------------------------------------------------------------%
filter_out(_, empty_lazy_list) = empty_lazy_list.
filter_out(P, lazy_list(X, LXs)) =
( if P(X) then
filter_out(P, value(LXs))
else
cons(X, (func) = filter_out(P, value(LXs)))
).
%-----------------------------------------------------------------------------%
foldl(_, empty_lazy_list, A) = A.
foldl(F, lazy_list(X, LXs), A) = foldl(F, value(LXs), F(X, A)).
%-----------------------------------------------------------------------------%
foldr(_, empty_lazy_list, A) = A.
foldr(F, lazy_list(X, LXs), A) = F(X, foldr(F, value(LXs), A)).
%-----------------------------------------------------------------------------%
foldr_lazy(_, empty_lazy_list, A) = A.
foldr_lazy(F, lazy_list(X, LXs), A) =
F(X, susp((func) = foldr_lazy(F, value(LXs), A))).
%-----------------------------------------------------------------------------%
take(N, Xs) =
( if N > 0, Xs = lazy_list(X, LXs) then
cons(X, (func) = take(N - 1, value(LXs)))
else
empty_lazy_list
).
%-----------------------------------------------------------------------------%
drop(N, Xs) =
( if N > 0, Xs = lazy_list(_, LXs) then
drop(N - 1, value(LXs))
else
Xs
).
%-----------------------------------------------------------------------------%
take_while(_, empty_lazy_list) = empty_lazy_list.
take_while(P, lazy_list(X, LXs)) =
( if P(X) then
cons(X, (func) = take_while(P, value(LXs)))
else
empty_lazy_list
).
%-----------------------------------------------------------------------------%
drop_while(_, empty_lazy_list) = empty_lazy_list.
drop_while(P, Xs @ lazy_list(X, LXs)) =
( if P(X) then
drop_while(P, value(LXs))
else
Xs
).
%-----------------------------------------------------------------------------%
take_until(_, empty_lazy_list) = empty_lazy_list.
take_until(P, lazy_list(X, LXs)) =
( if P(X) then
empty_lazy_list
else
cons(X, (func) = take_until(P, value(LXs)))
).
%-----------------------------------------------------------------------------%
drop_until(_, empty_lazy_list) = empty_lazy_list.
drop_until(P, Xs @ lazy_list(X, LXs)) =
( if P(X) then
Xs
else
drop_until(P, value(LXs))
).
%-----------------------------------------------------------------------------%
ints(Lo, Hi) =
( if Lo =< Hi then
cons(Lo, (func) = ints(Lo + 1, Hi))
else
empty_lazy_list
).
ints_with_step(Lo, Hi, Step) =
( if Lo =< Hi then
cons(Lo, (func) = ints_with_step(Lo + Step, Hi, Step))
else
empty_lazy_list
).
ints_from(Lo) =
cons(Lo, (func) = ints_from(Lo + 1)).
ints_from_with_step(Lo, Step) =
cons(Lo, (func) = ints_from_with_step(Lo + Step, Step)).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
% lazy_primes.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Tue May 5 13:33:30 EST 2009
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
%-----------------------------------------------------------------------------%
:- module lazy_primes.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is cc_multi.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- implementation.
:- import_module int.
:- import_module lazy.
:- import_module lazy_list.
:- import_module list.
:- import_module solutions.
:- import_module string.
%-----------------------------------------------------------------------------%
main(!IO) :-
io.command_line_arguments(Args, !IO),
( if
Args = []
then
Max = 100
else if
Args = [MaxStr],
string.to_int(MaxStr, Max0)
then
Max = Max0
else
io.format(stderr_stream,
"usage: lazy_primes max\n assuming 100\n", [], !IO),
Max = 100
),
InRange = ( pred(X::in) is semidet :- X =< Max ),
PrintPrime = ( pred(X::in, IO0::di, IO::uo) is det :-
format("%d ", [i(X)], IO0, IO)
),
Primes = lazy_list.take_while(InRange, primes),
solutions.unsorted_aggregate(enumerate_nondet(Primes), PrintPrime, !IO),
io.nl(!IO).
%-----------------------------------------------------------------------------%
:- pred enumerate_nondet(lazy_list(int)::in, int::out) is nondet.
enumerate_nondet(lazy_list(X, LXs), Y) :-
(
Y = X
;
enumerate_nondet(value(LXs), Y)
).
%-----------------------------------------------------------------------------%
:- func primes = lazy_list(int).
primes = primes_2(ints_from(2)).
%-----------------------------------------------------------------------------%
:- func primes_2(lazy_list(int)) = lazy_list(int).
primes_2(empty_lazy_list) = empty_lazy_list.
primes_2(lazy_list(X, LXs)) =
cons(X, (func) = primes_2(filter_out(multiple_of(X), value(LXs)))).
%-----------------------------------------------------------------------------%
:- pred multiple_of(int::in, int::in) is semidet.
multiple_of(X, Y) :- Y mod X = 0.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions: mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the developers
mailing list