List Comprehensions, Custom Operators, Typed Holes

Something Fun: List Comprehensions

Haskell has list comprehensions, a nice syntax for defining lists that combines the power of map and filter. Remember that in chapter 12 we did list comprehensions in Python. Haskell’s work pretty much the same way, but their syntax is a bit different.

For instance, look at the following list comprehension in Python:

[2*i for i in [1,2,3]]

An equivalent list comprehension in Haskell would be written as:

[2*i | i<-[1,2,3]]
    ==> [2,4,6]

Note that this is very similar to using the function map:

map (2*) [1,2,3]

Moreover, you can also use filters in list comprehensions, similar to how you can add an if statement inside a list comprehension in python. For instance:

[i for i in range(1,8) if i % 2==0]

Would be written in Haskell using list comprehension as:

Filtering:

[i | i <- [1..7], even i]
    ==> [2,4,6]

Note that this is another way of writing:

map id (filter even [1..7])

In general, these two forms are equivalent:

[f x | x <- lis, p x]
map f (filter p lis)

List comprehensions can do even more. You can iterate over multiple lists:

[ first ++ " " ++ last | first <- ["John", "Mary"], last <- ["Smith","Cooper"] ]
    ==> ["John Smith","John Cooper","Mary Smith","Mary Cooper"]

You can make local definitions:

[ reversed | word <- ["this","is","a","string"], let reversed = reverse word ]
    ==> ["siht","si","a","gnirts"]

You can even do pattern matching in list comprehensions!

firstLetters string = [ char | (char:_) <- words string ]

firstLetters "Hello World!"
    ==> "HW"

Something Fun: Custom Operators

In Haskell an operator is anything built from the characters !#$%&*+./<=>?@\^|-~. Operators can be defined just like functions (note the slightly different type annotation):

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

Something Useful: Typed Holes

Sometimes when writing Haskell it can be tricky to find expressions that have the right type. Luckily, the compiler can help you here! A feature called Typed Holes lets you leave blanks in your code, and the compiler will tell you what type the expression in the blank should have.

Blanks can look like _ or _name. They can be confused with the “anything goes” pattern _, but the difference is that a hole occurs on the right side of a =, while an anything goes pattern occurs on the left side of a =.

Let’s start with a simple example in GHCi:

Prelude> filter _hole [True,False]

<interactive>: error:
    • Found hole: _hole :: Bool -> Bool
        Or perhaps ‘_hole’ is mis-spelled, or not in scope
    • In the first argument of ‘filter’, namely ‘_hole’
        In the expression: filter _hole [True, False]
        In an equation for ‘it’: it = filter _hole [True, False]
    • Relevant bindings include
        it :: [Bool] (bound at <interactive>:5:1)
        Valid hole fits include
        not :: Bool -> Bool
            (imported from ‘Prelude’
            (and originally defined in ‘ghc-prim-0.6.1:GHC.Classes’))
        id :: forall a. a -> a
            with id @Bool
            (imported from ‘Prelude’ (and originally defined in ‘GHC.Base’))

The important part of this message is the very first line. This tells you what type Haskell is expecting for the hole.

<interactive>: error:
    • Found hole: _hole :: Bool -> Bool

The rest of the error message offers some suggestions for the value of _hole, for example id and not.

Let’s look at a longer example, where we try to implement a function that filters a list using a list of booleans:

keepElements [5,6,7,8] [True,False,True,False] ==> [5,7]

We’ll start with zip since we know that pairs up the elements of the two lists nicely. We add a typed hole _doIt and call it with the result of zip to see what we need to do next.

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = _doIt (zip xs bs)

<interactive>: error:
    • Found hole: _doIt :: [(a, Bool)] -> [a]
    ...

That looks like something that could be done with map. Let’s see what happens:

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map _f (zip xs bs)

<interactive>: error:
    • Found hole: _f :: (a, Bool) -> a
    ...
        Valid hole fits include
        fst :: forall a b. (a, b) -> a

Great! GHC reminded us of the function fst that grabs the first out of a pair. Are we done now?

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (zip xs bs)

Prelude> keepElements [5,6,7,8] [True,False,True,False]
[5,6,7,8]

Oh right, we’ve forgotten to do the filtering part. Let’s try a typed hole again:

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (filter _predicate (zip xs bs))

<interactive>: error:
    • Found hole: _predicate :: (a, Bool) -> Bool
    ...
        Valid hole fits include
        snd :: forall a b. (a, b) -> b
        ...
        ... lots of other suggestions

Again GHC has reminded us of a function that seems to do the right thing: just grab the second element out of the tuple. Now our function is finished and works as expected.

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (filter snd (zip xs bs))

Prelude> keepElements [5,6,7,8] [True,False,True,False]
[5,7]

Remember typed holes when you get stuck with type errors when working on the exercises! Try replacing a function or variable with a typed hole. It might help you figure out what you need.

Exercises

All exercises can be found in Set3a and Set3b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 3a:

You can check your current points from the blue blob in the bottom-right corner of the page.