Function definition has type error in function many

Question

I recently started learning Haskell and I am currently working through the "Higher Order Functions for Parsing" paper. You can find it Here.

The paper defines a function called many.

many :: parser * ** -> parser * [**]
many p = ((p $then many p) $using cons) $alt (succeed [])

I am trying to convert it to Haskell.

succeed v inp = [(v, inp)]

fail' inp = []

satisfy p [] = fail' []
satisfy p (x:xs)
  | p x = succeed x xs
  | otherwise = fail' xs

literal x = satisfy (==x)

alt' p1 p2 = \inp -> p1 inp ++ p2 inp

then' p1 p2 = \inp -> [((v1, v2), out2) | (v1, out1) <- p1 inp, (v2, out2) <- p2 out1]

using' p f = \inp -> [(f v, out) | (v, out) <- p inp]

many' p = ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])

I have tested all the pieces in isolation and they work fine. But the definition of many is giving me error. I can't seem to figure out what is the issue. I am doing exactly how it's mentioned in the paper.

Main.hs:19:56: error:
    • Couldn't match type ‘[a0]’ with ‘[(a, b)] -> [(a, b)]’
      Expected type: t -> [([(a, b)] -> [(a, b)], t)]
        Actual type: t -> [([a0], t)]
    • In the second argument of ‘alt'’, namely ‘(succeed [])’
      In the expression:
        ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])
      In an equation for ‘many'’:
          many' p = ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])
    • Relevant bindings include
        p :: t -> [(a, t)] (bound at Stum.hs:19:7)
        many' :: (t -> [(a, t)]) -> t -> [(b, t)] (bound at Stum.hs:19:1)
   |
19 | many' p = ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])
   | 
Failed, no modules loaded.
Prelude>

In the future, please do not include images of text (code, error messages, etc.) unless the question specifically relates to text color, font, etc. Images of text are not accessible to visually impaired people and impede searching. — dfeuer

Carl Carl · Accepted Answer · 2021-01-15T12:09:55

This would be a lot easier to follow if you had types on all your top-level definitions.

Regardless, I think the problem is in the interaction between using' and currying. I note that then' parses two values into a pair, and the sample code you're following parses applies cons to that pair to create a list from the pair elements as the head and tail of the list. But (:) is curried - if you apply it to a pair, the pair is just the head of the list, and it still expects a second argument for the tail. You should decide whether you want using' to take a curried function or not. If you want to stick as close to the paper you're following as possible, you'll leave the definition of using', but change many' to

many' p = ((p `then'` (many' p)) `using'` uncurry (:)) `alt'` (succeed [])

uncurry is a simple helper function exposed by Prelude that just happens to solve exactly this issue.

Note: all this is unchecked. It's the best quick guess I can provide without seeing the types involved.

Here's a bit more explanation to try to make this more understandable:

(:) has the type a -> [a] -> [a]. uncurry (:) (or equivalently, (\(h, t) -> h:t), in case uncurry is a bit much to wrap your head around at once) has the type (a, [a]) -> [a]. That difference should be what you keep in mind as you work through the rest.

Note that then' tuples up the parsed values in ((v1, v2), out2). Note that using' transforms the parsed value as a whole in (f v, out). When those get chained together, it ends up evaluating an expression along the lines of f (v1, v2). Given how many' will use then', v1 is going to be a single parse result, and v2 will be a list of subsequent parse results. You want to combine those together into a bigger list, (v1:v2). You need to do that by applying some function f to (v1, v2). Now go back to the difference between (:) and uncurry (:). Only one of those will have the right type to do that when provided as f.

I hope this expanded explanation makes it a bit easier to see what's going on.

Function definition has type error in function many

1 Answers