To slightly alter the question, is there a way to define a class<div><div><br></div><div>> class (Functor f) => Fixpoint f x where</div><div>> ...</div><div><br></div><div>so that I can define something with a type signature that looks like</div>
<div><br></div><div>> something :: (Fixpoint f x) => ... x ...</div><div><br></div><div>which will accept any</div><div><br></div><div>> argument :: F (F (F ... (F a) ... ))</div><div><br></div><div>in place of x?</div>
<div><br></div><div>Or alternatively could something analogous be done with type families?</div><div><br></div><div>Thanks,</div><div>Sebastien</div><div><br><div class="gmail_quote">On Mon, May 7, 2012 at 5:45 PM, Sebastien Zany <span dir="ltr"><<a href="mailto:sebastien@chaoticresearch.com" target="_blank">sebastien@chaoticresearch.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Thanks Wren!<div><br></div><div>When I try</div><div>> fix term</div><div>ghci complains of an ambiguous type variable.</div>
<div><br></div><div>I have to specify</div><div>> term :: (Expr (Expr (Expr (Fix Expr))))</div>
<div>for it to work.</div><div><br></div><div>Is there a way around this?</div><div class="HOEnZb"><div class="h5"><div><br><div class="gmail_quote">On Sun, May 6, 2012 at 4:04 PM, wren ng thornton <span dir="ltr"><<a href="mailto:wren@freegeek.org" target="_blank">wren@freegeek.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div>On 5/6/12 8:59 AM, Sebastien Zany wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
Suppose I have the following types:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
data Expr expr = Lit Nat | Add (expr, expr)<br>
newtype Fix f = Fix {unFix :: f (Fix f)}<br>
</blockquote>
<br>
I can construct a sample term:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
term :: Expr (Expr (Expr expr))<br>
term = Add (Lit 1, Add (Lit 2, Lit 3))<br>
</blockquote>
<br>
But isn't quite what I need. What I really need is:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
term' :: Fix Expr<br>
term' = Fix . Add $ (Fix . Lit $ 1, Fix . Add $ (Fix . Lit $ 2, Fix . Lit<br>
</blockquote>
$ 3))<br>
<br>
I feel like there's a stupidly simple way to automatically produce term'<br>
from term, but I'm not seeing it.<br>
</blockquote>
<br></div></div>
There's the smart constructors approach to building term' in the first place, but if someone else is giving you the term and you need to convert it, then you'll need to use a catamorphism (or similar).<br>
<br>
That is, we already have:<br>
<br>
Fix :: Expr (Fix Expr) -> Fix Expr<br>
<br>
but we need to plumb this down through multiple layers:<br>
<br>
fmap Fix :: Expr (Expr (Fix Expr)) -> Expr (Fix Expr)<br>
<br>
fmap (fmap Fix) :: Expr (Expr (Expr (Fix Expr)))<br>
-> Expr (Expr (Fix Expr))<br>
<br>
...<br>
<br>
If you don't know how many times the incoming term has been unFixed, then you'll need a type class to abstract over the n in fmap^n Fix. How exactly you want to do that will depend on the application, how general it should be, etc. The problem, of course, is that we don't have functor composition for free in Haskell. Francesco's suggestion is probably the easiest:<br>
<br>
instance Functor Expr where<br>
fmap _ (Lit i) = Lit i<br>
fmap f (Add e1 e2) = Add (f e1) (f e2)<br>
<br>
class FixExpr e where<br>
fix :: e -> Fix Expr<br>
<br>
instance FixExpr (Fix Expr) where<br>
fix = id<br>
<br>
instance FixExpr e => FixExpr (Expr e) where<br>
fix = Fix . fmap fix<br>
<br>
Note that the general form of catamorphisms is:<br>
<br>
cata :: Functor f => (f a -> a) -> Fix f -> a<br>
cata f = f . fmap (cata f) . unFix<br>
<br>
so we're just defining fix = cata Fix, but using induction on the type term itself (via type classes) rather than doing induction on the value term like we usually would.<span><font color="#888888"><br>
<br>
-- <br>
Live well,<br>
~wren</font></span><div><div><br>
<br>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>