Understanding the function signature
I read the article and one of the most fundamental parts of it is the following function, written in Haskell:
fixP :: Eq a => (Parser a -> Parser a) -> Parser a
fixP h x = fixS f
where f s = h p x
where p y = if x == y then s
else fixP h y
My Haskell is rusty. As I understand it fixP
takes 1 argument, which is a function Parser a -> Parser a
where it a
has a constraint on defining equality. However, the pattern matches two arguments, h
and x
. What's called x
?
Additional types of signatures are used:
type Parser a = State -> Set (a,State)
type State = String
type Set a = [a]
fixS :: Eq a => (Set a -> Set a) -> Set a
After reading and understanding the answer and for everyone interested; here's a function written in javascript:
function fixP(h) {
return function(x) {
var f = function(s) {
var p = function(y) {
if(x == y) {
return s;
} else {
return fixP(h)(y);
}
};
return h(p)(x);
};
return fixS(f);
};
}
source to share
Note that it fixP h
has a type Parser a
. Since it Parser a
is a synonym State -> Set (a, State)
, we see what fixP h
is actually a function:
(fixP h) :: State -> Set (a, State)
Therefore, we can apply this function to some x
type argument State
. It looks like (fixP h) x
. Since the function app remains associative , it is the (fixP h) x
same as fixP h x
.
In words: To define what is fixP
, we define what it does with the arguments, i.e. define what it is fixP h
. Since it is fixP h
itself a function, we need to define it. We define it by specifying what it does with the arguments, i.e. We define what it is (fixP h) x
. The left associativity of the function application means that the latter can be written fixP h x
.
As for the "what x?" Question: its a type State
, so it smells like some kind of parser state, which according to the type of synonyms you gave is a string. Exactly what this string role is, although it is not clear only from the types :)
source to share