Haskell Learning

Use Functor in the definition of Applicative

For example, when defining <*> for Parser, you need:

(<*>) :: Parser (a -> b) -> Parser a -> Parser b

You only need to work to get the (a -> b) from the first argument. After that, you can use fmap to transform Parser a to Parser b.

My original implementation:

Parser {runParser = pf} <*> Parser {runParser = px} =
	Parser $ \s -> join $ fmap (\(f, s') -> fmap (first f) (px s')) (pf s)

I had to do fmap (first f) (px s') i.e., unpack the Maybe (a, String) type again despite doing it once for Functor.

-- After some help from an existing implementation:
Parser {runParser = pf} <*> xp =
    Parser (join . fmap (\(f, s') -> runParser (fmap f xp) s') . pf)

Why Algebraic Data Types Matter

Will Kurt gives a good example for ADTs vs OOP class hierarchies by trying to represent names.

XMonad

To get the classname for an application, run:

xprop | grep WM_CLASS

and click on the application window. Use the second term. The first one doesn’t seem to work.

WM_CLASS(STRING) = "emacs25", "Emacs"

So, use “Emacs”, not “emacs25”.

Turtle

[2018-03-15 Thu] First impressions: pretty cool!

Each utility like ls or grep is basically a function that takes a stream of lines (Shell Line) and returns a stream of lines. Mix and match to your heart’s delight.

Beautiful Folds

Combining HashMaps by combining their values (not just picking the first value for a key), averaging, creating custom Monoid types for aggregating statistics: http://tech.frontrowed.com/2017/09/22/aggregations/

Of course, Gabriel has a post on this: http://www.haskellforall.com/2013/08/composable-streaming-folds.html

Row Polymorphism

From Brian McKenna’s blog:

Here’s a simple example of where the row instantiation can cause differences:

let f x = x with {sum: x.a + x.b}
let answer = f {a: 1, b: 2, c: 100}

With structural subtyping, the type is upcast to what f needs and we get back:

answer :: {a: Number, b: Number, sum: Number}

But with row polymorphism, the row variable \(\rho\) gets instantiated to contain the c field:

answer :: {a: Number, b: Number, c: Number, sum: Number}

My hypothesis: You need row polymorphism only because you’re changing data types on the fly without specifying in advance which parts you want to change.

The idiomatic way to do this would be to build a data structure that explicitly allows for change.

A simple example is data Tree a = Leaf a | Branch (Tree a) (Tree a). This data structure allows you to change the data type stored at each node from Person to String or Int without any other changes, i.e., Tree Person to Tree String. The type parameter a in the type definition makes it explicit that changes in the data type are orthogonal to changes in the structure of the tree. Moreover, it does not allow for any other ad hoc changes.

That’s my problem with row polymorphism! It doesn’t restrict the changes you can make to the data type. It seems to act like you have no idea how you will change the data type and like it must therefore be open to anything you might do.

(I haven’t gone deep into this topic. These are just my initial thoughts.)

The only good argument I’ve heard so far for row polymorphism has been “extensible effects” as seen in PureScript. I’m not sure how useful that is but it seems cool and I’ll look into it soon.

Arrows

Hypothesis: Arrows allow you to compose disparate operations on a data structure so that it still seems like a single operation.

(***) :: Arrow a => a b c -> a b' c' -> a (b, b') (c, c')

You can, of course, compose arrows to get a single arrow:

(<<<) ::
  forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
  Control.Category.Category cat =>
  cat b c -> cat a b -> cat a c

(All arrows are categories.)

Finally, you can raise a plain function into an arrow:

arr :: Arrow a => (b -> c) -> a b c

Arrow laws:

Identity law: Raising an identity operation should just give you the identity arrow (I think).

arr id === id

Composition law: Composing two functions and then raising them to an arrow should be the same as raising them to arrows and then composing them.

arr (f . g) === arr f <<< arr g

For example:

*Main Control.Arrow> arr (+1) <<< arr (* 2) $ 5
11
*Main Control.Arrow> arr ((+1) . (*2)) $ 5
11

How do arrows simplify code?

This part of the wiki (https://en.wikibooks.org/wiki/Haskell/Understanding_arrows#Static_and_dynamic_parsers) talks about using static and dynamic parsers to prevent space leaks.

Hypothesis: Arrows allow you to combine two different types of parsers and treat them as one.

Couldn’t you do that with monads? Not sure. Haven’t thought it through.

Test: [2022-05-09 Mon] Reading The Fun of Programming, edited by Jeremy Gibbons and Oege de Moor.

Apparently, an Arrow is a Category with a one-sided product function, called first.

class Category c where
    id :: c a a
	(>>>) :: c a b -> c b d -> c a d

They need to satisfy identity and associativity.

class Arrow c where
    pure :: (a -> b) -> c a b
	(>>>) :: c a b -> c b d -> c a d
	first :: c a b -> c (a, d) (b, d)

first means that it took an arrow from a to b and turned it into an arrow from (a, d) to (b, d).

idA is uniquely determined by the pure id.

Arrow instance for functions:

class Arrow (->) where
    pure :: (a -> b) -> (a -> b)
	(>>>) :: (a -> b) -> (b -> d) -> (a -> d)
	first :: (a -> b) -> (a, d) -> (b, d)

Arrow instance for State:

newtype State s i o = ST ((s, i) -> (s, o))

class Arrow (State s) where
    pure :: (i -> o) -> (State s i o)
	(>>>) :: (State s i o) -> (State s o o2) -> (State s i o2)
	first :: (State s i o) -> (State s (i, d) (o, d))

Here, pure f is just ST (id x f). That is, the state part remains unchanged, while f is append to the input.

ST f >>> ST g is just ST (g . f).

first f is just ``.

Watch Tests

stack test –file-watch –fast

Super-slow. Takes around 10 seconds to rebuild and test.

Apparently, ghcid can essentially reload ghci and check for errors. That works. However, I’m not able to get it to run tests upon reloading.

Odds and Ends

Int to Hex

Prelude Data.Bits Numeric Data.Char> let showIntAsHex n = showIntAtBase 16 intToDigit n “”

Haskell Tooling

[2023-05-08 Mon] Failed to install stylish-haskell.

Questions

What is higher-rank polymorphism?

Useful Haskell Resources

Thinking Functionally with Haskell by Richard Bird. The Sudoku implementation is compact and epic. Reminds me of PG.

TODO: Check out http://haskellbook.com/

Recursion schemes: https://www.schoolofhaskell.com/user/bartosz/understanding-algebras; http://www.timphilipwilliams.com/slides.html - Recursion schemes by example (very detailed)