<div dir="ltr">You can use a general fold and unfold, without any type-specific programming if you re-express Expr as the least fixed point of its underlying "base functor":<br><br>> data ExprF a = Add a a | Sub a a | Mul a a | Eq a a | B Bool | I Int<br>
> deriving (Show,Functor)<br>><br>> data Expr = Fix ExprF<br><br>Then use the standard definitions:<br><br>> newtype Fix f = Roll { unRoll :: f (Fix f) }<br>> <br>> fold :: Functor f => (f b -> b) -> (Fix f -> b)<br>
> fold h = h . fmap (fold h) . unRoll<br>> <br>> unfold :: Functor f => (a -> f a) -> (a -> Fix f)<br>> unfold g = Roll . fmap (unfold g) . g<br><br>Also handy:<br><br>> hylo :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)<br>
> hylo h g = fold h . unfold g<br><br>For details, see Jeremy Gibbons's paper "Calculating functional programs". There are probably easier sources as well.<br><br><div><div>-- Conal<br><br></div></div></div>
<div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Mar 30, 2013 at 11:45 AM, J. J. W. <span dir="ltr"><<a href="mailto:bsc.j.j.w@gmail.com" target="_blank">bsc.j.j.w@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>Dear all,</div><div><br></div><div>I was wondering whether it was possible to write fold expressions more elegantly. Suppose I have the following</div><div>datastructure:</div><div><br></div><div>data Expr = Add Expr Expr</div>
<div> | Sub Expr Expr</div><div> | Mul Expr Expr</div><div> | Eq Expr Expr</div><div> | B Bool</div><div> | I Int</div><div> deriving Show</div><div> </div>
<div>
type ExprAlgebra r = (r -> r -> r, -- Add</div><div> r -> r -> r, -- Sub</div><div> r -> r -> r, -- Mul</div><div> r -> r -> r, -- Eq</div>
<div> Bool -> r, -- Bool</div><div> Int -> r -- Int</div><div> )</div><div> </div><div>foldAlgebra :: ExprAlgebra r -> Expr -> r</div>
<div>foldAlgebra alg@(a, b, c ,d, e, f) (Add x y) = a (foldAlgebra alg x) (foldAlgebra alg y)</div><div>foldAlgebra alg@(a, b, c ,d, e, f) (Sub x y) = b (foldAlgebra alg x) (foldAlgebra alg y)</div><div>foldAlgebra alg@(a, b, c ,d, e, f) (Mul x y) = c (foldAlgebra alg x) (foldAlgebra alg y)</div>
<div>foldAlgebra alg@(a, b, c ,d, e, f) (Eq x y) = d (foldAlgebra alg x) (foldAlgebra alg y)</div><div>foldAlgebra alg@(a, b, c ,d, e, f) (B b') = e b'</div><div>foldAlgebra alg@(a, b, c ,d, e, f) (I i) = f i</div>
<div><br></div><div>If I am correct, this works, however if we for example would like to replace all Int's by booleans (note: this is to illustrate my problem):</div><div><br></div><div>replaceIntByBool = foldAlgebra (Add, Sub, Mul, Eq, B, \x -> if x == 0 then B False else B True)</div>
<div><br></div><div>As you can see, a lot of "useless" identity code. Can I somehow optimize this? Can someone give me some pointers how I can write this more clearly (or with less code?) So I constantly don't have to write Add, Sub, Mul, for those things that I just want an "identity function"?</div>
<div><br></div><div>Thanks in advance!</div><div><br></div><div>Jun Jie</div></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>