Skip to main content

(Un)ordinary type-fu in Haskell

· 7 min read

I'm progressing with my learning of Haskell. After grasping basic concepts time has come to face more challenging stuff.

There are several "patterns" on the intermediate level and all make heavy use of types. The tennets are to reduce typing and making more generalized abstractions. They come at cost of upfront learning time and are hard to grasp really.

This time I tackled 2 topics: structural pattern and then generics. I managed to combine these two in one post, so I will share it today.

Motivating example​

So let's start with something simple. You want to model complex numbers with a datatype. Like for example:

data Pair = MkPair {
    first :: Int,
    second :: Int
}
    deriving (Show, Eq)

What is immediately obvious is that if you wanted to have Pair for Double then you would have to write duplicate record definition. Better to generalize to all numbers:

data (Num f) => Pair f = MkPair {
    first :: f,
    second :: f
}
    deriving (Show, Eq)

Because we are interested only numerical values we limit f to the types instantiating Num type class: (Num f) => Pair f = MkPair.

But then you realize that you also need a class for complex numbers.

data (Num f) => Complex f = MkComplex {
    real :: f,
    imag :: f
}
    deriving (Show, Eq)

It is almost identical but carries different meaning. That's actually good that Haskell type system is nominal (new name means new type).

But these types are identical regarding the structure. What if we could actually compare Pair and Complex with the same method?

What GHC.Generic's do under the hood​

To simulate (and duplicate) functionality in GHC itself we will implement the mechanism for just one specific case. We start by implementing typeclass that is an interface for extracting generic structure.

class Generic a where
    type Rep a :: Type
    from :: a -> Rep a
    to :: Rep a -> a

Generic typeclass has associated type that each instance will implement. This type is our "structure". Rep a is connocalized type and to and from methods convert back and forth.

Then each type that want's the representation canonicalized will have to implement it. We can do it for your two types.

instance (Num f) => Generic (Complex f) where
    type Rep (Complex f) = (f, f)
    from (MkComplex r i) = (r, i)
    to (r, i) = MkComplex r i

instance (Num f) => Generic (Pair f) where
    type Rep (Pair f) = (f, f)
    from (MkPair r i) = (r, i)
    to (r, i) = MkPair r i

As you can see for both types we "strip off" data type and represent it as plain product type = tuple.

Then how do we approch equality checking? We implement generalized version geq.

geq :: (Generic a, Generic b, Rep a ~ Rep b, Eq (Rep a)) => a -> b -> Bool
geq x y = from x == from y

So our function geq requires that (of course) type is implementing Generic type class. Then this is interesting:

Rep a ~ Rep b, Eq (Rep a) - we limit function to compare only those generic instances that have equal representation types (ie. (,))

geq x y = from x == from y - compare representations

Let's check:

ghci> :{
ghci| let x = MkComplex { real = 1, imag = 1}
ghci|     y = MkPair { first = 1, second = 1}
ghci| in x `geq` y
ghci| :}
True

And other one:

ghci> :{
ghci| let x = MkPair { first = 1.0, second = 1.0 }
ghci|     y = MkComplex { real = 2.0, imag = 2.0 }
ghci| in x `geq` y
ghci| :}

False

Part 2: Higher Kinded Data Types​

We will learn here structural pattern for reading in and validating forms. It makes heavy use of Applicative and the fact that we can "curry" generated constructor for a record.

The idea of HKD is simple - parametrize type by "container", ie.

data  Person f = MkPerson {
    firstName :: f String,
    lastName :: f String,
    age :: f Int
}

What does it gives us? Let's see the type of constructor:

ghci> :t MkPerson
MkPerson :: f String -> f String -> f Int -> Person f

If f is an Applicative and most usually it is we can use <*> curry each step of constructor operating on record fields.

Let's read in the data:

readString :: IO (Maybe String)
readString = do
    str <- fmap strip getLine
    return $ case str of
        "" -> Nothing
        _ -> Just str

readInt :: IO (Maybe Int)
readInt = do
    s <- readString
    return $ s >>= readMaybe


readPerson :: IO (Person Maybe)
readPerson = MkPerson
    <$> readString
    <*> readString
    <*> readInt

The logic is simple: in case of string if is empty string return Nothing and in case of int unparsable number gives Nothing as well. So we used structural pattern for the first time. At each step reading function is applied so constituents IO (Maybe String) and IO (Maybe Int) get turned into IO (Person Maybe) eventually.

Then we would like the following: if some field is nothing apply the defaults instead.

defaults :: Person Maybe
defaults = MkPerson {
    firstName = Just "John",
    lastName = Just "Doe",
    age = Just 30
}

applyDefaults :: IO (Person Maybe) -> IO (Maybe (Person Identity))
applyDefaults p = do
    p' <- p
    return (MkPerson
        <$> fmap Identity (firstName p' <|> firstName defaults)
        <*> fmap Identity (lastName p' <|> lastName defaults)
        <*> fmap Identity (age p' <|> age defaults))

If we run for example:

ghci> let p = MkPerson {firstName = (Just "Dominik"), lastName = (Just "Gawlik"), age = (Just 34)}
ghci> fmap Identity (firstName p)
Just (Identity {runIdentity = "Dominik"})

We can see that it flips Maybe with Idenity in a smart way.

  1. We extract the Maybe from the record by autogenerated field-method
  2. fmap applies Identity constructor inside Maybe

So basically what we did with the above code is that we ascertain that all the fields are Maybe's Just other way around we would get nothing.

So the last step is to serialize the record into something with similar structure

data PersonFinal = MkPersonFinal {
    firstName' :: String,
    lastName' :: String,
    age' :: Int
}
    deriving (Show)

serialize :: Person Identity -> PersonFinal
serialize p = MkPersonFinal {
    firstName' = runIdentity (firstName p),
    lastName' = runIdentity (lastName p),
    age' = runIdentity (age p)
}

Now let's test it.

runIO = do
    p <- applyDefaults readPerson
    print $ fmap serialize p
ghci> runIO

gawlik

Just (MkPersonFinal {firstName' = "John", lastName' = "gawlik", age' = 30})

And we get what we wanted.

Conclusion​

Structural pattern is intemediate-level Haskell code that comes in handy. It is useful to know about it if you will read some packages in the future. We touched Higher Kinded Data Types and some typing ticks to make generics work similar way to GHC.

Reading:

Thanks.