Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

Re^5: Derangements iterator (callbacks)

by Anonymous Monk
on Jan 01, 2006 at 18:21 UTC ( #520270=note: print w/replies, xml ) Need Help??

in reply to Re^4: Derangements iterator (callbacks)
in thread Derangements iterator

From enumerators to cursors: turning the left fold inside out...
The mechanical inversion procedure presented in * had a catch: it relies on shift/reset (or call/cc plus a mutable cell, which is the same thing). How can we do such an inversion in Haskell? We can introduce a right fold enumerator, which is more amenable to such transformations. Or we can use a continuation monad and emulate shift/reset. The present article demonstrates the third approach: a non-recursive left-fold. We argue that such a left fold is the best interface for a collection. Indeed, given the non-recursive left-fold we can:
  • instantiate it into the ordinary left fold
  • instantiate in into a stream
If we turn two enumerators into streams, we can *safely* interleave these streams.

We should point out that the relation between the left fold, the non-recursive left fold and the stream is deep. The ordinary, recursive left fold is the fix point of the non-recursive one. On the other hand, the instantiation of the non-recursive left fold as a stream, as we shall see, effectively captures a continuation in a monadic action. We see once again that call/cc and Y are indeed two sides of the same coin **.

The rest of the article demonstrates the inversion procedure. The procedure is generic, as evidenced by its polymorphic type. We illustrate the technique on an example of a file considered a collection of characters. Haskell provides a stream interface to that collection: hGetChar. We implement a left fold enumerator. We then turn that enumerator back to a stream: we implement a function 'myhgetchar' _only_ in terms of the left fold enumerator. The approach is general and uses no monadic heavy lifting.

  • Comment on Re^5: Derangements iterator (callbacks)

Replies are listed 'Best First'.
Re^6: Derangements iterator (callbacks)
by demerphq (Chancellor) on Jan 02, 2006 at 12:33 UTC

    Well, seeing as apparently you understand this article maybe you could give us an example how to turn foreach (@list){ ... } into a cursor based approach. Since perl doesnt support first class continuations I guess you will need to implement this "left fold" operator. Which in itself would be pretty interesting. Actually even explaining in normal english (unlike the functional jargon gobbly-gook that the article uses) what this "left fold" operator does would be nice.


      #!/usr/bin/perl -w # A non-recursive left fold (foldl), taken from Language::Functional sub foldl(&$$) { my($f, $z, $xs) = @_; map { $z = $f->($z, $_) } @{$xs}; return $z; } # Recursive foldl sub foldl_rec { my($f, $z, $xs) = @_; my($head, @tail) = @$xs; $head ? foldl_rec($f, $f->($z,$head), \@tail) : $z; } # "Fold" is the universal list traversal function. Also known as # "reduce" (see List::Util) and "accumulate" (C++ STL). Any function # you write that munges lists (map, grep, etc.) can be rewritten in # terms of a fold. It essentially takes a list and replaces each "con +s" # constructor with a function. Stated another way, if you have a list # @a = (1, 2, 3, 4), fold will replace the commas with another functio +n # of your choosing. Let's say you want the sum of the elements in @a. # Replace the commas with a '+' sign, (1 + 2 + 3 + 4). Easy isn't it? # You might write it as... $s = foldl(sub{ $_[0] + $_[1] }, 0, [1..4]); print "sum = $s\n"; # 10 # addition to providing the function and the list, you supply an # initial value to start out with. In the case of $sum above, we use # 0. If you want the product of the elements in the list you can chan +ge # to... $p = foldl(sub{ $_[0] * $_[1] }, 1, [1..4]); print "product = $p\n"; # 24 # The "left" portion comes into play because we start at the left end +of # the list and work towards the right. The actual sum that is # calculated is (((((0+1)+2)+3)+4). It only makes a difference when t +he # function used isn't associative. Subtraction is an example... $l = foldl(sub{ $_[0] - $_[1] }, 0, [1..4]); print "left fold subtraction = $l\n"; # ((((0-1)-2)-3)-4) == -10 # Recursive foldr sub foldr_rec { my($f, $z, $xs) = @_; my($head, @tail) = @$xs; $head ? $f->($head,foldr_rec($f, $z, \@tail)) : $z; } $r = foldr_rec(sub{ $_[0] - $_[1] }, 0, [1..4]); print "right fold subtraction = $r\n"; # (1-(2-(3-(4-0)))) == -2 # The dual of "fold" is the universal list creation function, "unfold" +. # See more unfold in action... # #
      Actually even explaining in normal english (unlike the functional jargon gobbly-gook that the article uses) what this "left fold" operator does would be nice.
      Another explaination of the original paper.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://520270]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (3)
As of 2017-08-22 04:09 GMT
Find Nodes?
    Voting Booth?
    Who is your favorite scientist and why?

    Results (328 votes). Check out past polls.