[Haskell-cafe] Idiomatic usage of the fixpoint library

[Roman Leshchinskiy]

Roman Cheplyaka wrote:
>
>     {-# LANGUAGE TypeFamilies, FlexibleContexts, UndecidableInstances,
> FlexibleInstances #-}
>     import Data.Fixpoint
>
>     newtype Expr = Expr { unExpr :: Pre Expr Expr }
>
>     instance Functor (Pre Expr) => Fixpoint Expr where
>         data Pre Expr a
>             = Add a a
>             | Const Int
>         project = unExpr
>         inject = Expr
>
>     instance Functor (Pre Expr) where
>         fmap f (Const x) = Const x
>         fmap f (Add x1 x2) = Add (f x1) (f x2)
>
>     eval = cata eval' where
>         eval' (Const x) = x
>         eval' (Add x1 x2) = x1 + x2
>
> There are some issues with this code, compared to simply using
>
>     newtype Fix f = In { out :: f (Fix f) }
>
> to build an Expr.
>
> 1. Since 'Pre' is a data (not type) family, we cannot simply make use of
>    a functor defined elsewhere. We need to define the functor inside the
>    instance declaration (or at least wrap an existing functor).

Yes, it would be nicer if it was a type family. There is a single reason
why this isn't the case but I find that reason pretty compelling: you
couldn't type hylo if it was.

> 2. I wasn't able to derive the Functor instance, getting an error
>
>         Derived instance `Functor (Pre Expr)'
>           requires illegal partial application of data type family Pre
>         In the data type instance declaration for `Pre'

That's really a GHC problem. There is no reason why it shouldn't be able
to do this.

> 3. Having to use UndecidableInstances makes me feel a bit uncomfortable.

You don't need UndecidableInstances. Just get rid of the Functor (Pre
Expr) constraint on the Fixpoint Expr instance, it's doesn't do anything
anyway.

Roman