Haskell: Creating Type Classes for Lightning

Question

So, I read a little about the Zipper template in Haskell (and other functional languages, I suppose) to navigate and change the data structure, and I thought it would be a good chance for me to hone my skills when creating type classes in Haskell, since the class can provide a general workaround interface for me to write code, regardless of the data structure passed.

I thought that I probably needed two classes: one for the root data structure and one for the special data structure created to go through the first:

module Zipper where class Zipper z where go'up :: z -> Maybe z go'down :: z -> Maybe z go'left :: z -> Maybe z go'right :: z -> Maybe z class Zippable t where zipper :: (Zipper z) => t -> z get :: (Zipper z) => z -> t put :: (Zipper z) => z -> t -> z 

But when I tried them with some simple data structures like a list:

 -- store a path through a list, with preceding elements stored in reverse data ListZipper a = ListZipper { preceding :: [a], following :: [a] } instance Zipper (ListZipper a) where go'up ListZipper { preceding = [] } = Nothing go'up ListZipper { preceding = a:ps, following = fs } = Just $ ListZipper { preceding = ps, following = a:fs } go'down ListZipper { following = [] } = Nothing go'down ListZipper { preceding = ps, following = a:fs } = Just $ ListZipper { preceding = a:ps, following = fs } go'left _ = Nothing go'right _ = Nothing instance Zippable ([a]) where zipper as = ListZipper { preceding = [], following = as } get = following put z as = z { following = as } 

Or a binary tree:

 -- binary tree that only stores values at the leaves data Tree a = Node { left'child :: Tree a, right'child :: Tree a } | Leaf a -- store a path down a Tree, with branches not taken stored in reverse data TreeZipper a = TreeZipper { branches :: [Either (Tree a) (Tree a)], subtree :: Tree a } instance Zipper (TreeZipper a) where go'up TreeZipper { branches = [] } = Nothing go'up TreeZipper { branches = (Left l):bs, subtree = r } = Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } go'up TreeZipper { branches = (Right r):bs, subtree = l } = Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } go'down TreeZipper { subtree = Leaf a } = Nothing go'down TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } = Just $ TreeZipper { branches = (Right r):bs, subtree = l } go'left TreeZipper { branches = [] } = Nothing go'left TreeZipper { branches = (Right r):bs } = Nothing go'left TreeZipper { branches = (Left l):bs, subtree = r } = Just $ TreeZipper { branches = (Right r):bs, subtree = l } go'right TreeZipper { branches = [] } = Nothing go'right TreeZipper { branches = (Left l):bs } = Nothing go'right TreeZipper { branches = (Right r):bs, subtree = l } = Just $ TreeZipper { branches = (Left l):bs, subtree = r } instance Zippable (Tree a) where zipper t = TreeZipper { branches = [], subtree = t } get TreeZipper { subtree = s } = s put zs = z { subtree = s } 

I could not compile it, I would get as many errors as this for each of the Zippable instance Zippable :

  Zipper.hs: 28: 14:
     Couldn't match expected type `z '
            against inferred type `ListZipper a '
       `z 'is a rigid type variable bound by
           the type signature for `zipper 'at Zipper.hs: 10: 20
     In the expression: ListZipper {preceding = [], following = as}
     In the definition of `zipper ':
         zipper as = ListZipper {preceding = [], following = as}
     In the definition for method `zipper '

So I'm not sure where to go from here. I suspect my problem is that I am trying to link the two instances together when the declaration (Zipper z) => just wants z be any Zipper .

Answer 1

(Other than that, your go'up notation ... is inventive. The Haskell style is usually camelCase.)

You are on the right track. What you wrote is equivalent to the following.

 {-# LANGUAGE RankNTypes #-} instance Zippable [a] where zipper = ... :: forall z. (Zipper z) => [a] -> z get = ... :: forall z. (Zipper z) => z -> [a] set = ... :: forall z. (Zipper z) => z -> [a] -> z 

(For all z types defined by Zipper z , there is zipper :: [a] -> z .)

You are trying to define zipper = ... :: [a] -> ListZipper a , which is clearly too restrictive.

Your code will look with the following minimal changes:

 {-# LANGUAGE MultiParamTypeClasses #-} class (Zipper z) => Zippable zt where zipper :: t -> z get :: z -> t set :: z -> t -> z instance Zippable (ListZipper a) [a] where ... instance Zippable (TreeZipper a) (Tree a) where ... 

See classes with several parameters . This extension is after Haskell'98, but the Haskell implementation widely supports it.

Answer 2

You can also use families of type synonyms instead of classes with several parameters and functional dependencies. In such cases, they offer a cleaner and more understandable solution. In this case, the class and instance will look like this:

 class Zippable t where type ZipperType t :: * enter :: t -> ZipperType t focus :: ZipperType t -> t instance Zippable [a] where type ZipperType [a] = ListZipper a enter = ... focus = ... 

Fun with type functions is a great introduction to the family of type synonyms for people already familiar with Haskell. I also wrote an article on how several families of type synonyms can often be used instead of functional dependencies some time ago.

Hope this helps!