Tag Archives: Haskell

Whole Haskell Use of GADTs

For some reason GADTs are a particular sticking point for many advocates of Simple Haskell. But sometimes GADTs are the natural form of expressing a concept.

By way of example, here’s a snippet of API I’ve borrowed from JuicyPixels:

data Image a = Image {
    imageWidth :: !Int,
    imageHeight :: !Int,
    imageData :: Vector (PixelBaseComponent a)

data DynamicImage =
    ImageY8 (Image Pixel8) |
    ImageY16 (Image Pixel16) |
    ImageY32 (Image Pixel32) |
    ImageYF (Image PixelF) |
    ImageYA8 (Image PixelYA8) |
    ImageYA16 (Image PixelYA16) |
    ImageRGB8 (Image PixelRGB8) |
    ImageRGB16 (Image PixelRGB16) |
    ImageRGBF (Image PixelRGBF) |
    ImageRGBA8 (Image PixelRGBA8) |
    ImageRGBA16 (Image PixelRGBA16) |
    ImageYCbCr8 (Image PixelYCbCr8) |
    ImageCMYK8 (Image PixelCMYK8) |
    ImageCMYK16 (Image PixelCMYK16)

promoteImage :: ColorConvertible a b => Image a -> Image b 

JuicyPixels was originally released in 2012, and there’s always a good presumption against changing an API, so we can’t blame the developers for not making use of GADTs. But if we were starting a project like this from scratch today, how would we write such code, using the whole language?

The way DynamicImage has been defined makes it a bit difficult to work with. For example, if you want to get the width or height of a dynamic image, you’ll have to write cases for each constructor. And the convertibility from one pixel type to another is encoded at the type level (with ColorConvertible), but there’s no clean way to do it at the value level, if we wanted to provide that functionality dynamically.

We can make this code more expressive, and more elegant, by using a GADT that represents the pixel type of a dynamic image:

data PixelType a where
    PixelType8 :: PixelType Pixel8
    PixelType16 :: PixelType Pixel16
    PixelType32 :: PixelType Pixel32
    PixelTypeF :: PixelType PixelF
    PixelTypeYA8 :: PixelType PixelYA8
    PixelTypeYA16 :: PixelType PixelYA16
    PixelTypeRGB8 :: PixelType PixelRGB8
    PixelTypeRGB16 :: PixelType PixelRGB16
    PixelTypeRGBF :: PixelType PixelRGBF
    PixelTypeRGBA8 :: PixelType PixelRGBA8
    PixelTypeRGBA16 :: PixelType PixelRGBA16
    PixelTypeYCbCr8 :: PixelType PixelYCbCr8
    PixelTypeCMYK8 :: PixelType PixelCMYK8
    PixelTypeCMYK16 :: PixelType PixelCMYK16

data DynamicImage = forall a. DynamicImage (PixelType a) (Image a)

Any code to get properties of the contained Image is now much simpler:

dynamicImageSize :: DynamicImage -> (Int, Int)
dynamicImageSize (DynamicImage _ img) = (imageWidth img, imageHeight img)

We can also express convertibility dynamically, if we want to add that:

canPromotePixel :: PixelType a -> PixelType b -> Maybe (Dict (ColorConvertible a b))
-- provided as appropriate

promoteDynamicImage :: DynamicImage -> PixelType b -> Maybe (Image b)
promoteDynamicImage (DynamicImage pta img) ptb = do
    Dict <- canPromotePixel pta ptb
    return $ promoteImage img

You can see how with Haskell’s fancy shiny GADT feature, the code is now more expressive, and easier to understand for anyone who knows the language.

GADTs are actually not a particularly difficult concept to learn, for someone who already understands rank-n types and existential quantification. And in many situations, they provide a huge benefit in expressibility.

— Ashley Yakeley

Whole Haskell is Best Haskell

The promise of Haskell over other languages is that it allows you to more cleanly and intuitively represent the application domain. This leads to more intelligible and maintainable code. But to take full advantage of what Haskell has to offer, you have to embrace the whole language. This means making use of any appropriate language feature, just as you would with any other language.

If you’re using Haskell in industry, it’s my belief that restricting your team to some “simple” subset of the language for complex problems will make your code more complex and more difficult for competent developers to understand. It will be more likely to have repetitive boilerplate, and more likely to require explicit error calls to handle “impossible” cases. It will be less comprehensible, and so less maintainable.

Here are some claims from “The Simple Haskell Initiative”, which I believe are flawed:

Fancy Haskell is costly to teams because it usually takes more time to understand and limits the pool of people who can effectively contribute.

By taking this attitude, you are not only committing your code to mediocrity, but your team too. Whole, elegant, Haskell, firing on all language cylinders, takes less time for competent developers to understand. And you can raise less-experienced developers to the necessary competence specific to your project.

Things that have been around longer will be more well-tested and understood by a larger group of people. Prefer tried and true techniques over the latest shiny library or language feature. The more foundational something is in your tech stack, the more conservative you should be about adopting new versions or approaches to that thing.

These are two separate things.

For libraries, maturity is certainly a valid concern. But it is unrelated to the structure of the library’s API.

For language features, the GHC team has a high bar for releasing new extensions, often involving formal proof. The implementation of features considered “fancy”, such as GADTs, type families, and polykinds, is understood to be as sound as that of any other part of the language. They are unlikely to be a particular source of compiler defects.

If you adopt a new thing, how much of its complexity will spread throughout the rest of your codebase? You should be more hesitant to adopt something if its complexity is going to spread through a larger portion of your codebase.

Code written in whole Haskell is less complex than “simple” Haskell for the same complex application. That’s the whole point of it.

There is no one definition of what language features count as “Simple Haskell”. Michael Snoyman seeks to define a “boring” subset of Haskell, but his recommended set of “boring” language extensions is quite broad, including most extensions relating to classes and type families, and even PolyKinds. Boring Haskell, in practice, seems to be close to Whole Haskell.

Sam Halliday, by contrast, seeks a vastly more restricted language, rejecting GADTs, type families, multi-parameter classes, and apparently even rank-n types and existential quantification. Such restrictions lead to unnecessarily complicated code, in my view. Here’s a simple example of how GADTs and existential data quantification can improve code generality and intelligibility.

What you should be doing

  • Embrace the whole language.
  • Set a high quality bar for code within your team.
  • Mentor less-experienced developers.

Embrace the whole language. Pretty much every “fancy” feature of the whole GHC Haskell language has a productive purpose. That’s the point of all the academic research. As a competent Haskell developer, you should know when that purpose applies and how to make best use of each feature.

Note that language features are not exactly the same as language extensions. For example, the language gives you the option to either allow or prohibit “incoherent” use of class instances. In most cases, the best use of this language feature is to prohibit, as it can ensure a discipline that leads to more intelligibility and predictability.

Some language features are of relatively specialised use. Polykinded types are very useful for type-oriented applications (such as implementing a typed language interpreter). And, of course, some simpler or more straightforward projects might make use of relatively few language features.

Set a high quality bar for code within your team. Set code expectations as early as you can. Discuss ideas early, and make suggestions for design approaches. Haskell makes refactoring easier than many languages, take advantage of that as appropriate.

Mentor less-experienced developers. When you hire a Java, Python, or C++ developer, you can expect them to be fully competent in each of those languages. You can typically give them development ownership of progressively larger project features, and leave them to get on with it until code review. Given the current state of the Haskell job market, this may not be the case for Haskell developers.

If you hire junior developers who are not yet familiar with the whole language, you will need to mentor them. Take extra time with them to explain how features of the Haskell language work, how they are best used in general, and how you use them in your codebase.

If that sounds like an extra burden, bear in mind that not many developers make the effort to learn Haskell in the first place, and those that do are likely to have more aptitude to learn more about it. Invest in the people you hire. If you’re doing anything worthwhile, you’re in this for the long term.

… Why did you choose Haskell, anyway?

— Ashley Yakeley

Forbidden Haskell Types

Sometimes, writing Haskell is like having an argument with the compiler. You give it your reasoning, and it checks it over for flaws. And if it thinks it finds one, it will tell you all about it. You then have to look over what it told you, and figure out exactly what its complaint is. Did I just express myself badly? Or am I actually wrong? Or, very occasionally, the compiler is just being petulant and you have to work around it. Of course, if you’re really upset about GHC not accepting your perfectly reasonably argued program, you can go tell its parents.

Haskell’s type system is pretty great, but one thing it doesn’t have, that some other type systems do have, is recursive types, by which I mean, types directly constructed from themselves. Recursive types are forbidden in Haskell.

Let’s say we want to create a recursive type T = Maybe T. The official introductory Haskell answer to this is that one cannot do this directly, but one can easily create a type T that contains Maybe T, sometimes called a “newtype wrapper”. Like this:

newtype T = MkT (Maybe T)

Simple enough. But can we do better than this? Can we create a type T that is actually equal to Maybe T? Can we create the forbidden recursive type?

Let’s start with won’t work:

type T = Maybe T
Example.hs:6:1: error:
    Cycle in type synonym declarations:
      Example.hs:6:1-16: type T = Maybe T

The type keyword creates an alias for a type, and aliases cannot be recursive as they must eventually refer to an actual type.

Oddly enough, GHC does accept this:

type family T where
    T = Maybe T

Type families are strange things. They’re not quite “real” types, but neither are they mere aliases for types, as they don’t have to be fully resolved. Indeed you can declare a type family in one module, use it all over as if it were a real type, and then define the actual instances of that family in another module.

Sadly, though, GHC won’t let us actually use the instance. It rejects the obvious proof that T and Maybe T are the same type:

type family T where
    T = Maybe T

proof :: T :~: Maybe T
proof = Refl
Example.hs:10:9: error:
    • Reduction stack overflow; size = 201
      When simplifying the following type: T

Why is this? It’s because GHC can’t just accept what it’s been told, and instead endlessly tries to “reduce” (that is, expand) T = Maybe T = Maybe (Maybe T) etc, giving up when it reaches a safety limit. You can think of it as a kind of intellectual black hole, or an “infohazard” for the compiler: if it ever starts examining the strange secrets of your recursive type, it will get lost in the infinite abyss, until a built-in emergency mechanism kicks it awake after it’s twisted in the vortex 200 times (you can change this number if you want, or even let it run forever).

It turns out we can construct a type T together with a proper (non-bottom) proof value of T :~: Maybe T, we just have to be discreet. The key is to make sure GHC never comes across the unfathomable constraint T ~ Maybe T, because it will immediately become ensnared in the contemplation of its endlessness.

Instead, we prepare a lemma that is both harmless and more general, and then carefully specialise it to get the terrifying conclusion we want, using the TypeApplications extension, thus avoiding the need for any kind of inference:

type family A p q where
    A () x = Maybe (A x ())

lemma :: forall x. (A () x) :~: Maybe (A x ())
lemma  = Refl

type T = A () ()

proof :: T :~: Maybe T
proof = lemma @()

Actually constructing and deconstructing values of T will require a similar circumspection. The trick is, we don’t let GHC infer types. We musn’t let GHC think, because thinking about the bad thing leads it to madness. Instead, we apply all types by hand. Here’s the full program, including all the necessary extensions:

{-# LANGUAGE RankNTypes, TypeApplications, TypeOperators,
    TypeFamilies, UndecidableInstances, AllowAmbiguousTypes #-}
module Main where
import Data.Type.Equality

type family A p q where
    A () x = Maybe (A x ())

lemma :: forall x. (A () x) :~: Maybe (A x ())
lemma  = Refl

type T = A () ()

proof :: T :~: Maybe T
proof = lemma @()

convert1 :: forall a b. a :~: b -> a -> b
convert1 Refl = id

convert2 :: forall a b. a :~: b -> b -> a
convert2 Refl = id

tconvert1 :: T -> Maybe T
tconvert1 = convert1 @T @(Maybe T) proof

tconvert2 :: Maybe T -> T
tconvert2 = convert2 @T @(Maybe T) proof

nothing :: T
nothing = tconvert2 $ Nothing @T

just :: T -> T
just x = tconvert2 $ Just @T x

count :: T -> Int
count t = case tconvert1 t of
    Nothing -> 0
    Just t' -> succ $ count t'

t3 :: T
t3 = just $ just $ just nothing

main :: IO ()
main = putStrLn $ show $ count t3

This program defines a truly recursive type T = Maybe T, constructs a value of it, and then deconstructs that value. (It does indeed correctly print “3”.) On the other hand, it’s much more complicated than just using a newtype like we’re supposed to…

— Ashley Yakeley

With-Resource Puzzle

If you want to use a file in Haskell, you have two options. You can open and close the file yourself:

openFile :: FilePath -> IOMode -> IO Handle
hClose :: Handle -> IO ()

… or you can use a function that takes care of the open-close lifecycle:

withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r

Which is the better interface? It’s a trade-off: withFile guarantees that every open file is closed, while openFile and hClose allow you to open and close files in any order.

Let’s create types to represent these two kinds of interface:

type OpenClose h = IO (h,IO ()) -- opens a resource, returns a handle and a "closer"
type With h = forall r. (h -> IO r) -> IO r

openCloseFile :: FilePath -> IOMode -> OpenClose Handle
openCloseFile path mode = do
    h <- openFile path mode
    return (h, hClose h)
withFile :: FilePath -> IOMode -> With Handle
-- already defined

Is it possible to convert between the two? Here’s how to obtain a With interface from an OpenClose interface:

openCloseToWith :: OpenClose h -> With h
openCloseToWith oc f = do
    (h, closer) <- oc
    finally (f h) closer

It’s also possible to obtain an OpenClose interface from a With interface. Can you see how?

withToOpenClose :: With h -> OpenClose h
withToOpenClose = ...?

(answer here)

(first posted here)

— Ashley Yakeley

Haskell Maxims and Arrows

I’ve been writing Haskell on and off since about 2001, including three years as a full-time job. This is what I’ve learnt…

  1. Haskell is the promise that you can write it as cleanly as your understanding of it. Have faith.
  2. Always be looking for patterns. Abstract them always and only when it simplifies.
  3. Persevere in getting an abstraction just right. When you find it, everything will magically fall into place.
  4. The implementation is the design.
  5. Hide whatever the caller shouldn’t care about. In particular, you can remove type parameters with appropriate quantification.
  6. There’s a reason fst3, snd3, thd3 are not in base. Triple or bigger: create a data type with fields instead.
  7. Never make an instance unless it morally follows the class’s rules.
  8. Instances of simpler classes are more valuable than of more complex generalisations.
  9. Monoid: not a flashy class, but still definitely worthwhile.
  10. Applicative: hugely underappreciated, and good for types that have “static information”. Lets you do deep magic with traverse and sequenceA.
  11. Monad: potential instances are usually easy to spot.
  12. The fewer type parameters in a class, the better. Can you turn any into associated types? Can you split the class into two classes? Can you hive off some of the parameters into a superclass?
  13. Don’t worry about strictness until it’s time to optimise.
  14. Intuition about optimisation tends to be bad. Before profiling, limit yourself to reasoning about complexity classes.
  15. An orphan instance is a very minor wart.
  16. Types themselves are weightless (i.e., erased). For example, * dropped from kind to type (with TypeInType) carries no information.
  17. You probably won’t need IORef.
  18. Template Haskell comes with a high cost in intelligibility. Sometimes it’s worth it.

— Ashley Yakeley