haskell - 了解函数签名

Question

我正在阅读a paper它最基本的部分之一是以下用 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

我的 Haskell 生锈了。据我了解，fixP需要1个参数，它是一个函数Parser a -> Parser a，其中a被限制为定义了相等性。但是该模式匹配 2 个参数:h 和 x。 x 指的是什么？

涉及的其他类型签名:

type Parser a = State -> Set (a,State)

type State = String

type Set a = [a]

fixS :: Eq a => (Set a -> Set a) -> Set a

<小时/>

阅读并理解答案后以及任何感兴趣的人；这是用 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);
    };
}

Answer 1

请注意，fixP h 的类型为 Parser a。由于 Parser a 是 State -> Set (a, State) 的同义词，我们看到 fixP h 实际上是一个函数:

(fixP h) :: State -> Set (a, State)

因此，我们可以将此函数应用于 State 类型的某个参数 x。看起来像 (fixP h) x。自 function application is left associative , (fixP h) x 与 fixP h x 相同。

换句话说:为了定义什么是 fixP，我们定义它对参数的作用，即我们定义什么 fixP h 是什么。由于fixP h本身就是一个函数，我们需要定义它。我们通过指定它对参数的作用来定义它，即我们定义 (fixP h) x 是什么。函数应用的左关联性意味着后者可以写成fixP h x。

关于问题“x是什么？”:它的类型是State，所以它闻起来像某种解析器状态，根据您给出的类型同义词，它是一个字符串。不过，仅仅从类型中还不清楚该字符串的确切作用:)