Sunday, October 18, 2015

Explicit is better than implicit

Many of the limitations associated with Haskell type classes can be solved very cleanly with lenses. This lens-driven programming is more explicit but significantly more general and (in my opinion) easier to use.

All of these examples will work with any lens-like library, but I will begin with the lens-simple library to provide simpler types with better type inference and better type errors and then later transition to the lens library which has a larger set of utilities.

Case study #1 - fmap bias

Let's begin with a simple example - the Functor instance for Either:

fmap (+ 1) (Right 2   ) = Right 3

fmap (+ 1) (Left "Foo") = Left "Foo"

Some people object to this instance because it's biased to Right values. The only way we can use fmap to transform Left values is to wrap Either in a newtype.

These same people would probably like the lens-simple library which provides an over function that generalizes fmap. Instead of using the type to infer what to transform we can explicitly specify what we wish to transform by supplying _Left or _Right:

$ stack install lens-simple --resolver=lts-3.9
$ stack ghci --resolver=lts-3.9
>>> import Lens.Simple
>>> over _Right (+ 1) (Right 2)
Right 3
>>> over _Right (+ 1) (Left "Foo")
Left "Foo"
>>> over _Left (++ "!") (Right 2)
Right 2
>>> over _Left (++ "!") (Left "Foo")
Left "Foo!"

The inferred types are exactly what we would expect:

>>> :type over _Right
over _Right :: (b -> b') -> Either a b -> Either a b'
>>> :type over _Left
over _Left :: (b -> b') -> Either b b1 -> Either b' b1

Same thing for tuples. fmap only lets us transform the second value of a tuple, but over lets us specify which one we want to transform:

>>> over _1 (+ 1)    (2, "Foo")
(3,"Foo")
>>> over _2 (++ "!") (2, "Foo")
(2,"Foo!")

We can even transform both of the values in the tuple if they share the same type:

>>> over both (+ 1) (3, 4)
(4,5)

Again, the inferred types are exactly what we expect:

>>> :type over _2
over _2 :: (b -> b') -> (a, b) -> (a, b')
>>> :type over _1
over _1 :: (b -> b') -> (b, b1) -> (b', b1)
>>> :type over both
over both :: (b -> b') -> (b, b) -> (b', b')

Case study #2 - length confusion

Many people have complained about the tuple instance for Foldable, which gives weird behavior like this in ghc-7.10 or later:

>>> length (3, 4)
1

We could eliminate all confusion by specifying what we intend to count at the term level instead of the type level:

>>> lengthOf _2   (3, 4)
1
>>> lengthOf both (3, 4)
2

This works for Either, too:

>>> lengthOf _Right (Right 1)
1
>>> lengthOf _Right (Left "Foo")
0
>>> lengthOf _Left  (Right 1)
0
>>> lengthOf _Left  (Left "Foo")
1

... and this trick is not limited to length. We can improve any Foldable function by taking a lens instead of a type class constraint:

>>> sumOf both (3, 4)
7
>>> mapMOf_ both print (3, 4)
3
4

Case study #3 - Monomorphic containers

fmap doesn't work on ByteString because ByteString is not a type constructor and has no type parameter that we can map over. Some people use the mono-foldable or mono-traversable packages to solve this problem, but I prefer to use lenses. These examples will require the lens library which has more batteries included.

For example, if I want to transform each character of a Text value I can use the text optic:

$ stack install lens --resolver=lts-3.9  # For `text` optics
$ stack ghci --resolver=lts-3.9
>>> import Control.Lens
>>> import Data.Text.Lens
>>> import qualified Data.Text as Text
>>> let example = Text.pack "Hello, world!"
>>> over text succ example
"Ifmmp-!xpsme\""

I can use the same optic to loop over each character:

>>> mapMOf_ text print example
'H'
'e'
'l'
'l'
'o'
','
' '
'w'
'o'
'r'
'l'
'd'
'!'

There are also optics for ByteStrings, too:

>>> import Data.ByteString.Lens
>>> import qualified Data.ByteString as ByteString
>>> let example2 = ByteString.pack [0, 1, 2]
>>> mapMOf_ bytes print example2
0
1
2

The lens approach has one killer feature over mono-foldable and mono-traversable which is that you can be explicit about what exactly you want to map over. For example, suppose that I want to loop over the bits of a ByteString instead of the bytes. Then I can just provide an optic that points to the bits and everyting "just works":

>>> import Data.Bits.Lens
>>> mapMOf_ (bytes . bits) print example2
False
False
False
False
False
False
False
False
True
False
False
False
False
False
False
False
False
True
False
False
False
False
False
False

The mono-traversable or mono-foldable packages do not let you specify what you want to loop over. Instead, the MonoFoldable and MonoTraversable type classes guess what you want the elements to be, and if they guess wrong then you are out of luck.

Conclusion

Here are some more examples to illustrate how powerful and general the lens approach is over the type class approach.

>>> lengthOf (bytes . bits) example2
24
>>> sumOf (both . _1) ((2, 3), (4, 5))
6
>>> mapMOf_ (_Just . _Left) print (Just (Left 4))
4
>>> over (traverse . _Right) (+ 1) [Left "Foo", Right 4, Right 5]
[Left "Foo",Right 5,Right 6]

Once you get used to this style of programming you begin to prefer specifying things at the term level instead of relying on type inference or wrangling with newtypes.

16 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Loving your blog, Sir ! Well done ! I also enjoy the way you do presentations - yesterday I was watching your speech about proofs at TNG. Is there any other videos with you ? would love to watch them ! thanks !

    ReplyDelete
    Replies
    1. Thanks! :)

      The only other recorded talks that I've done were these two (both on the same subject, but the latter talk went a little better in my opinion):

      * http://forwardjs.com/university/secure-execution-of-untrusted-scripts
      * http://begriffs.com/posts/2015-10-16-internet-of-code.html

      Delete
    2. I have watched http://begriffs.com/posts/2015-10-16-internet-of-code.html today and I have enjoyed it much. I believe the talk deserves more publicity ;-)

      Delete
  3. What an excellent article! I wonder to what other type classes a lens like approach could be applied?

    ReplyDelete
  4. Could you explain why in the composition of prisms the order is reversed?
    E.g. why its _Just . _Left in mapMOf_ (_Just . _Left) print (Just (Left 4)) ?
    Normally f . g means f gets applied after g...

    ReplyDelete
    Replies
    1. Looks like operator versions show a bit more intuitive order of things:
      > Just (Left 4) & _Just . _Left %~ show
      Just (Left "4")

      Delete
    2. This post might help explain why things work this way: http://www.haskellforall.com/2013/05/program-imperatively-using-haskell.html

      Delete
  5. The mono-foldable package is deprecated in favor of mono-traversable, so I think it is just confusing to mention them both.

    Also, one could easily infer a lot of things by "guessing". There is no guessing going on for mono-traversable, there is just one and only one explicitly pre-defined element type. One could say the same for the length instance of a tuple: that the instance is defined statically. I think the difference is 2-fold:

    1) A length of 1 for a tuple doesn't match up with expectations
    In contrast, we commonly think of Text as a list of characters and bytestrings as a list of bytes, so there is no surprise about "guessing" something else.
    2) Instance definitions are hidden from documentation.
    In contrast, the Element type is the very first piece of documentation that shows up in the haddocks:
    http://hackage.haskell.org/package/mono-traversable-0.10.0/docs/Data-MonoTraversable.html#t:Element
    You cannot use mono-traversable without knowing the monomorphic element type.

    I like the general concept of this article though. I prefer to use Bifunctor instead of Functor because to me it has never made sense to right-bias the Functor instance of Either.

    ReplyDelete
  6. Thank you for writing. I've learned a lot from your blog. And please do more of the video talks too. You speak very well.

    ReplyDelete
  7. Note though that there is still a certain level of implicitness in this method. For instance, the lenses `both` and `_1` are both defined in terms of type classes. On the other hand, I guess it doesn't hurt, because they are completely unambiguous. Perhaps that is the core of the matter, being implicit is a problem when you are implicit about something ambiguous, which is quite obvious now that I think of it.

    ReplyDelete
    Replies
    1. I'd also like to note that using newtypes is just another way of being explicit, one that is more verbose and less expressive.

      Delete
    2. That's why I used the `lens-family-core` library for the `both` and `_1` lens examples since it has more monomorphic types. So it's probably more accurate to say that lenses permit you to be more explicit but they can also be implicit as well (such as the `each` lens, which is very analogous to `monotraversable`)

      Delete
  8. This looks much better than the FTP hell.

    ReplyDelete