search

mndrix / list_util

Prolog list utility predicates
The Unlicense
11 stars 5 forks source link

More Laziness Needed in Higher Order Predicates #19

Closed eazar001 closed 9 years ago

eazar001 commented 9 years ago

Using the nice infrastucture we have, we can do things such as:

?- cycle([0,1,2], Cycle), take(5, Cycle, Take), maplist(plus(1), Take, Xs).
Xs = [1,2,3,1,2].

... which admittedly isn't so nice after glancing at it a second time. This is because it's doing twice the amount of work. There are nice utilities to counteract this effect, such as lazy_include/3 for example. In Haskell we can do:

take 5 . maplist (+1) $ [0..2]

This is all done in one pass thanks to the spirit of lazy evaluation that is built into the core functionality of Haskell's main implementation. In the above example take/3 is not the problem, since it is implemented in terms of split_at/4 which works quite well with lazy lists; it is maplist/3 that is making things very strict. There are a few ways of addressing this that crossed my mind. One way would be to create a lazy_maplist/3 to solve the problem in the spirit of your lazy_include/3. Another would be to simply make a variant of take/3 .... perphaps a take_with/4 of take_map/4, which synthesizes a solution from maplist/3 and take/3. Another option is to do both.

Either way, I wanted to catalog this issue to serve as a memorandum at the very least. Of peripheral interest: using [0..2] is very convenient syntax sugar. All the more reason to integrate your lazy incr/3 example into lazy_range/2 for the API. EDIT: I just noticed you implemented this with postive_integers/3.

eazar001 commented 9 years ago

The code below seems to obtain the exact desired behavior I described above earlier. When I get the chance I'll further test it for hitches or any weird cases, and push it with an actual test suite.

lazy_maplist(Goal, Xs, Ys) :-
  freeze(Ys, lazy_maplist_(Xs, Ys, Goal)).

lazy_maplist_([], [], _).
lazy_maplist_([X|Xs], [Y|Ys], Goal) :-
  call(Goal, X, Y),
  lazy_maplist(Goal, Xs, Ys).
mndrix commented 9 years ago

I would love to have lazy_maplist/3. Eventually, I'd like to have lazy variants of all the predicates in library(apply)

eazar001 commented 9 years ago

Yes, eventually getting all of apply in lazy form would be great. lazy_findall is also a great idea btw.