Search code examples
haskelltypestype-families

Type families - cannot derive Base Int?

The idea is to implement "lazy" length function to compare list length to a Int without computing the whole length.

{-# LANGUAGE DeriveFunctor
           , TypeFamilies
           , FlexibleInstances #-}
import Data.Functor.Foldable

type instance Base Int   = Maybe

Now we can have Foldable / Unfoldable

instance Foldable Int where
  project 0 = Nothing
  project x = Just (x-1)

instance Unfoldable Int where
  embed Nothing  = 0
  embed (Just x) = x+1

I want to convert [a] into Base Int Int:

leng :: [a] -> Base Int Int
leng = ana phi where
  phi :: [a] -> Base Int [a]
  phi []    = Nothing
  phi (_:t) = Just t

But this doesn't work. It complains [a] -> Base (Maybe Int) [a] is expected as type of phi. I don't understand why.

If that worked, then I can compare:

gt = curry $ hylo psi phi where
  phi (Just _, Nothing)  = Left True
  phi (Nothing, _)       = Left False
  phi (Just t, Just n)   = Right (t, n)

  psi (Left t)  = t
  psi (Right t) = t

main = print $ (leng [1..]) `gt` (ana project 4)

What's wrong with leng?

Solution

  • The type of ana is (a -> Base t a) -> a -> t. Note that it returns the plain t and not Base t t. So the correct type for leng is

    leng :: [a] -> Int