Advanced: Custom Types

Keelung already provides different Values & Expressions, but as a developer you may find it inconvenient to translate your structure in mind to these primitive types every time. Luckily, Keelung, despite being a DSL, supports custom datatype definitions in Haskell, as long as they are encode-able as combinations of Keelung primitive types (Field, Boolean, and UInt).

This might sounds a little crazy: you DON'T have to define the translations yourself! Just define a datatype and add some auxiliary lines, the Keelung library will derive the translations for you, thanks to the power of datatype-generic programming.

To define custom types, we need some understandings of Haskell datatypes, or more advancedly, GADTs. We also make use of the Haskell typeclass system.

Example

Let's look back at our Keelung example in the Merkle tree example that generates a Merkle tree:

module MerkleTree where

import Data.Foldable (foldlM)
import Hash.Poseidon
import Keelung

getMerkleProof :: Int -> Comp Field
getMerkleProof depth = do
  leaf     <- inputField Private
  siblings <- inputList2 Private depth 2
  indices  <- inputList Private depth :: Comp [Field]
  foldlM
    (\_digest (_i, p) -> hash p)
    leaf
    (zip indices siblings)

This program only generates a Field element that is the root of a Merkle tree. But what if we want a structure that actually represent the tree in question? A datatype that represents a Merkle tree in the form of Haskell datatype may look like this:

MTree.hs

module MTree where

import Keelung

data Tree a = Node a (Tree a) (Tree a) | Leaf a

type MerkleTree = Tree Field

And if we want to use MerkleTree in our Keelung programs, a function may have MerkleTree in its type signature:

buildMerkleTree :: Int -> Comp MerkleTree

This was not possible before Keelung v0.12.0, but since v0.12.0 we can achieve this with GHC.Generics, as long as the datatypes we define are encode-able into Fields, Booleans, UInts, or their combinations. We only need to modify MTree.hs a little bit to make buildMerkleTree possible:

MTree.hs

{-# LANGUAGE DeriveGeneric #-}

module MTree where

import Keelung

data Tree a = Node a (Tree a) (Tree a) | Leaf a
  deriving Generic

instance (Encode a) => (Encode (Tree a))

type MerkleTree = Tree Field

Notice that we only added three lines:

• {-# LANGUAGE DeriveGeneric #-} tells the Haskell compiler GHC that we want to use datatype-generic features, and

• deriving Generic after a data declaration generates its datatype-generic representation for us.

• instance (Encode a) => (Encode (Tree a)) looks like a Haskell instance definition without any implementations, which is exactly what it is. Keelung generates them for you, you are welcome! In English, this line means "If a is a type that can be encoded into Keelung, so is Tree a". Of course, we can declare this on simpler datatypes without parameters, e.g. instance Encode MerkleTree, which tells GHC to make MerkleTree encode-able into Keelung. But why make it ad-hoc when it can be as general as possible?

Remeber you have to make sure your datatype is encode-able with Keelung primitive types, this is enforced by the Encode typeclass. To know more about Encode, read the next section.

We can't promise every encode-able datatype is supported, but almost every one that is built upon primitive types is. See the instances of Generic in GHC.Generics for datatypes whose intances of Encode can be automatically generated.

The Encode Typeclass

To say some types are encode-able into Keelung, which is the prerequisite that they can be put in the Comp monad like the way it's in the signature of buildMerkleTree, we represent them with the Encode typeclass. E.g., we know MerkleTree is encode-able, because its elements (all of which are Fields in this case) are encode-able. we can define the instances ourselves, but the whole point of custom datatypes is to save you from this suffering.

Because Keelung has already defined Encode instances for primitive types, and generic instances for datatypes that are built on primitive types, GHC will check for you if the datatypes meet the conditions and generates the implementations automatically. For more information you may want look into its source code.