[Haskell-cafe] Newbie: Is‘type’ synonym hiding two much?

Dmitri O.Kondratiev dokondr at gmail.com
Thu Mar 22 11:13:00 EDT 2007

I am learning Haskell working through Simon Thompson book "Haskell The Craft
of Functional Programming" (second edition). Solving problems in the book
with more or less success I arrived almost to the end of the book at the
section 17.5 "Case study: parsing expressions".
Most probably the question I am going to ask here is very stupid, so please
bear with me. In any case, after going so far in the book I felt certain
that I know what function declaration means. So I thought that declaration:

F :: a -> b -> c

Is the same as:

F :: a -> (b -> c)

And means either:

-    a function 'f' of one argument of type 'a' that returns a function of
type (b -> c), or it can also be interpreted as:
-    a function 'f' of two arguments of type 'a' and 'b' returning value of
type 'c'

Now, in the 17.5 section of a book one may see the following declarations:

succeed :: b -> Parse a b

*Before looking at 'succeed' function definition* one may think that
'succeed' is a function of *one* argument of type 'b' that returns object of
type 'Parse a b'.

Yet, function definition given in the book is:

succeed val inp = [(val, inp)]

Looking at this definition, I am inclined to think that 'succeed' is a
function of *two*  arguments named 'val' and 'inp' in the definition !
How can such a definition be correct?

Ok, lets see what is this 'Parse a b' type is:

type Parse a b = [a] -> [(b, [a])]

So how does this help to make definition

'succeed val inp = [(val, inp)]'

sound right?

Well, the only way for me to make sense out of this is as follows.
In this case Haskell 'type' makes type synonym for the type:
[a] -> [(b, [a])]

In order not to get out of my mind I start thinking about 'type' as a macro
substitution mechanism. Then I do this substitution *myself as a Haskell
runtime* and get in the result the following declaration of a * real
function that Haskell runtime* works with:

Succeed :: b -> [a] -> [(b, [a])]

Great! This last declaration matches perfectly with function definition:

succeed val inp = [(val, inp)]

So I start feeling better, after all, it looks like my understanding of
Haskell function declarations is not flawed too much.
Well, but here comes my main questions! So:
1. Should I work every time as a macro translator when I just see *!any!*
function declaration?
2. Should I search through main and imported modules for treacherous 'type'
3. Where, in this case goes implementation abstraction principle? Why I must
provide *all* the details about function argument type structure in order to
understand how this function works?

Another example of a similar function from the book is:

alt :: Parse a b -> Parse a b -> Parse a b
alt p1 p2 inp = p1 inp ++ p2 inp

In function definition I see three parameters:
p1 – matches with function declaration perfectly
p2 – matches with function declaration perfectly
inp – how to match this parameter with function declaration ?

I can match 'inp' parameter with 'alt' function declaration *only* after
working as macro processor that expands type synonym 'Parse a b' into '[a]
-> [(b, [a])]' and getting *real* declaration:

alt :: [a] -> [(b, [a])] -> [a] -> [(b, [a])] -> [a] -> [(b, [a])]

with that matches

alt p1 p2 inp = p1 inp ++ p2 inp

where 'inp' matches with *last* '[a]' argument.

It seems that life of "human macro processor" becomes really hard when not
trivial functions with 'type' synonym arguments come into play!
Where I am wrong? Please enlighten me; I am really at a loss!
And thanks for reading all this!
Below I give a code example of these functions.


module Parser where

import Data.Char

type Parse a b = [a] -> [(b, [a])]

none :: Parse a b
none inp = []

succeed :: b -> Parse a b
succeed val inp = [(val, inp)]

suc:: b -> [a] -> [(b, [a])]
suc val inp = [(val, inp)]

spot :: (a -> Bool) -> Parse a a
spot p [] = []
spot p (x:xs)
     | p x = [(x, xs)]
     | otherwise = []

alt :: Parse a b -> Parse a b -> Parse a b
alt p1 p2 inp = p1 inp ++ p2 inp

bracket = spot (=='(')
dig = spot isDigit

t1 = (bracket `alt` dig) "234"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070322/ac6d68c1/attachment.htm

More information about the Haskell-Cafe mailing list