Threading a state through a fold?
Neelakantan Krishnaswami
Hello all,
I've been experimenting with using folds instead of pattern-matching,
so as to increase the abstractness of my code. By and large this works
great (keyword arguments are *enormously* useful), but there's one
problem that I haven't figured out how to solve yet.
Namely, I sometimes want to write a function in a state-passing style,
and I don't know how to do it elegantly with a regular fold. Here's a
concrete example, stripped down to its bare essentials:
Let's start with the type of lists (all this is in OCaml, btw):
type 'a lst = Nil | Cons of 'a * 'a lst
Now the fold function on this is also very simple:
let rec fold ~nil ~cons lst =
match lst with
Nil -> nil
| Cons(a, rest) -> cons a (fold nil cons rest)
So far, so good -- as everyone knows I can write many pattern matching
functions using the fold instead of explicit pattern-matching. Eg,
let rec map f lst =
match lst with
Nil -> Nil
| Cons(x, xs) -> Cons(f x, map f xs)
can instead become
let rec map' f lst =
fold
~nil: Nil
~cons: (let cons x xs = Cons(f x, xs) in cons)
lst
However, sometimes I want to thread some control information through
the functions I define, and at this point regular folds seem to stop
doing what I want. Eg, consider a function renumber which will simply
replace all the elements of the lst with a sequence of integers:
let rec renumber i lst =
match lst with
Nil ->
Nil, i
| Cons(x, xs') ->
let rest, i' = renumber i xs'
in Cons(i', rest), (i'+1)
This will turn the lst Cons('a', Cons('b', Cons('c', Cons('d', Nil))))
into the lst Cons(3, Cons(2, Cons(1, Cons(0, Nil)))), as well as
returning the transformed state i' = 4. (If all this seems contrived,
that's because it is. I've stripped this problem down from the real
one I'm facing.)
However, I can't replicate this behavior with a fold. In this case, I
seem to be stuck with using a reference cell to carry the info
out-of-band to emulate my desired behavior, like so:
let incr x =
let n = !x
in x := !x + 1; n
let renumber' i lst =
let x = ref i in
let lst' =
fold
~nil: Nil, !x
~cons: (let cons hd (tl, n) = Cons(incr x, tl) in cons)
lst
in (lst', !x)
Since this is comp.lang.functional, I doubt many of you will be
astonished if I report my dissatisfaction with this solution. The
only functional alternative I've found is to convert the fold into
continuation-passing style:
let rec kfold ~nil ~cons ~cont lst =
match lst with
Nil -> cont nil
| Cons(x, xs) ->
kfold
~nil: nil
~cons: cons
~cont: (function xs' -> cons x xs' cont)
xs
Thanks to CPS making the control flow is explicit, I can now directly
replicate the state-passing of the original renumber function:
let renumber'' i lst =
let cont v = v, i
in kfold
~nil: Nil
~cons: (let cons hd tl k =
let (tl', i') = k tl
in Cons(i', tl'), (i'+1)
in cons)
~cont: cont
lst
But I like this even less than using a reference, since it's at once
ugly and inefficient. There's gratuitous closure creation going on,
and it's especially unaesthetic to use them to manually create and
manage a stack when the runtime has one predefined. :)
Is there any trickery that I can do so that I can use the original
fold function but still get the state to thread properly?
Neel
Dana Harrington
Why not:
let rec renumber i lst =
fold
~nil: (Nil, i)
~cons: (fn x (xs,n) -> (Cons(n,xs),n+1))
lst
Neelakantan Krishnaswami
wrote:
>Neelakantan Krishnaswami wrote:
>>
>> However, I can't replicate this behavior with a fold. In this case, I
>> seem to be stuck with using a reference cell to carry the info
>> out-of-band to emulate my desired behavior, like so:
>
>Why not:
> let rec renumber i lst =
> fold
> ~nil: (Nil, i)
> ~cons: (fn x (xs,n) -> (Cons(n,xs),n+1))
> lst
Because I oversimplified and lost the part that causes the the
problem. :) Take a tree instead:
type 'a tree =
Leaf
| Node of 'a * 'a tree * 'a tree
with a fold
let rec fold ~leaf ~node tree =
match tree with
Leaf -> leaf
| Node(x, lft, rgt) -> node x (fold leaf node lft) (fold leaf node rgt)
An example tree might look like
let c = Node('a', Node('b', Leaf, Leaf), Node('c', Leaf, Leaf))
and we want to write a function that will return a tree with a number
from 1 to n at each node. With pattern matching it's easy:
let rec renumber tree i =
match tree with
Leaf ->
Leaf, i
| Node(x, l, r) ->
let l', i' = renumber l i in
let r', i'' = renumber r i'
in Node(i'', l', r'), (i'' + 1)
and so renumber c 0 yields:
Node(2, Node(0, Leaf, Leaf), Node(1, Leaf, Leaf)), 3
I don't see how to do the same tupling trick with a fold; my best
effort is
let renumber' i tree =
fold
~leaf: (Leaf, i)
~node: (let node x l r =
let (l', i' ) = l in (* Fold just passed i to each branch! *)
let (r', i'') = r (* This copies the state: wrong! *)
in
Node(i', l', r'), (i''+1) (* Obviously bogus. :[ *)
in node)
tree
which doesn't work because the fold function passes i to each branch
at a Node, effectively *copying* the state at each node -- calling
renumber' i c yields
Node(1, Node(0, Leaf, Leaf), Node(0, Leaf, Leaf)), 2
which is not what I want.
I'd like to ensure that i gets used in a single-threaded fashion using
a fold instead of explicit pattern matching, but don't know how to do
that. We didn't see the problem in the list example because each cons
cell only has one successor. We aren't this lucky with a tree.
Neel
Daniel C. Wang
> On Thu, 14 Jun 2001 12:14:42 -0600, Dana Harrington <dgha...@ucalgary.ca>
{stuff deleted}
> I'd like to ensure that i gets used in a single-threaded fashion using
> a fold instead of explicit pattern matching, but don't know how to do
> that. We didn't see the problem in the list example because each cons
> cell only has one successor. We aren't this lucky with a tree.
use the power of higher-order functions. i.e. use fold to compute a function
that renumbers the tree and passes the state appropiately. Here's some
sample ML code that shows the trick.
structure Tree =
struct
datatype 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
fun fold leaf node Leaf = leaf
| fold leaf node (Node (x,l,r)) =
node x (fold leaf node l) (fold leaf node r)
fun number_leaf i = (Leaf,i)
fun number_node _ l r i = let
val (l,i') = l i
val (r,i'') = r i'
in (Node(i'',l,r),i'' + 1)
end
fun number_tree t i = fold number_leaf number_node t i
val c = Node ("a",Node ("b",Leaf,Leaf),Node ("c",Leaf,Leaf))
val c' = number_tree c 0
end
Daniel C. Wang
"Daniel C. Wang" <danwan...@cs.princeton.edu> writes:
> use the power of higher-order functions. i.e. use fold to compute a function
> that renumbers the tree and passes the state appropiately. Here's some
> sample ML code that shows the trick.
For kicks here's a "monadic" version that uses a state monad. The fold
computes a monad which you then evaluate to get the result back. The state
monad is polymorphic so you can use it for any sort of state you want to
pass around.
The state monad is what you need to make fold more general.
Monads are useful even in non-pure langauges.
structure MTree =
struct
datatype 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
fun fold leaf node Leaf = leaf
| fold leaf node (Node (x,l,r)) =
node x (fold leaf node l) (fold leaf node r)
(* monadic combinators *)
datatype ('a,'b) S = S of 'a -> ('b * 'a)
fun eval (S m) s = m s
fun ret v = S (fn s => (v,s))
fun bnd m f = S (fn s => let
val (v,s) = eval m s
in eval (f v) s
end)
(* operations on the state *)
fun bndS m f = S (fn s => let
val (v,s) = eval m s
in eval (f (v,s)) s
end)
fun setS s' m = S (fn s => let
val (v,_) = eval m s
in (v,s')
end)
fun number_tree t i = let
val number_leaf = ret Leaf
fun number_node _ lm rm =
bnd lm (fn l =>
bndS rm (fn (r,i) =>
setS (i+1)
(ret (Node(i,l,r)))))
in eval (fold (ret Leaf) number_node t) i
end
Neelakantan Krishnaswami
wrote:
>
>"Daniel C. Wang" <danwan...@cs.princeton.edu> writes:
>>
>> use the power of higher-order functions. i.e. use fold to compute a
>> function that renumbers the tree and passes the state
>> appropiately. Here's some sample ML code that shows the trick.
>
> For kicks here's a "monadic" version that uses a state monad. The
> fold computes a monad which you then evaluate to get the result
> back. The state monad is polymorphic so you can use it for any sort
> of state you want to pass around.
>
> The state monad is what you need to make fold more general. Monads
> are useful even in non-pure langauges.
Thanks! This is exactly the hint I needed, and the code is *very*
pretty. I am happy, and will continue to be so until I run into my
next roadblock. :)
Neel