CODEWITHSUNDEEP
haskell
gogurt
gogurt

Reputation: 831

Notational confusion in a basic type declaration exercise

I'm going through the new book Haskell Programming from First Principles. It seems decent, but I feel that there are some confusing holes in the explanations. I apologize if I'm missing something basic.

The last problem in chapter 5 is to fill in the ??? below so that things make sense:

munge :: (x -> y) -> (y -> (w, z)) -> x -> w
munge = ???

The solution which was explained to me (after much head-scratching) goes:

g :: y -> (w, z)
g = undefined

f :: x -> y
f = undefined

munge :: (x -> y) -> (y -> (w, z)) -> x -> w
munge g f v = fst (g (f v))

I'm getting hung up on this example in two ways.

First, it seems like the munge function ought to take a function as input which takes x -> y. But the way munge is defined, it seems like we supply an additional argument v to the function f first. But if f :: x -> y, then won't the expression f v be of type just y instead of x -> y?

Second, I'm struggling to understand why the x appears in the second-to-last position in the type declaration. At that point I feel like the logical next piece after the (y -> (w,x)) step should just be w, since at that stage the function g is being applied to fst and w ought to be the type of what fst returns. I can feel that I'm close, but can't quite close the gap.

Clearly I'm not understanding the notation correctly. Can anyone set me straight?

EDIT: Ok, here is a clarifying question to the second part. Is it possible to revise the munge function so that it has the following type (i.e. original type with second-to-last x application omitted)? If so what would it look like?

munge :: (x -> y) -> (y -> (w, z)) -> w

Upvotes: 0

Views: 87

Answers (2)

chepner
chepner

Reputation: 531245

The solution, confusingly, is using the same variables f and g for two different things: as global names for two functions, and as parameter names in defining munge. Making a change of variable should make it clearer:

g :: y -> (w, z)
g = undefined

f :: x -> y
f = undefined

munge :: (x -> y) -> (y -> (w, z)) -> x -> w
munge f1 f2 v = fst (f2 (f1 v)) -- fst . f2 . f1 $ v

Then you would call munge on f and g will thing like

munge f g someArgumentForF

Inside munge, f (called f1) is first applied to someArgumentForF (called v) to get a value that can be passed to g (called f2). This produces a tuple, and applying fst to the tuple returns the value of type w needed as the final result.

Upvotes: 2

jberryman
jberryman

Reputation: 16645

The answer is incorrect and ill-typed. f and g should be swapped:

munge :: (x -> y) -> (y -> (w, z)) -> x -> w
munge g f v = fst (f (g v))

I'm not sure if that clears up your confusion.

EDIT In case it's interesting, here are more equivalent ways of writing this function and its type:

-- notice parens in type signature; `->` associates right
munge :: (x -> y) -> ((y -> (w, z)) -> (x -> w))
munge g f v = -- omitted

-- type signature omitted
munge boop _plort zOWY = fst (_plort (boop zOWY))

munge g f = fst . f . g

munge g = \f v -> fst . f . g $ v

-- don't do this please
munge = ((fst .) .) . (.)

EDIT2 It might be helpful to play around with this in GHCi, asking the inferred type of different expressions:

Prelude> let munge g f v = fst (f (g v))
Prelude> :t munge
munge :: (t1 -> t) -> (t -> (a, b)) -> t1 -> a
Prelude> :t munge head
munge head :: (t -> (a, b)) -> [t] -> a
Prelude> :t munge head (\x-> (x, not x))
munge head (\x-> (x, not x)) :: [Bool] -> Bool
Prelude> :t munge ((+1) . fst . snd . head)
munge ((+1) . fst . snd . head)
  :: Num t => (t -> (a, b)) -> [(a1, (t, b1))] -> a

Upvotes: 4

Related Questions