一个非常基本的Haskell查询

Question

在没有任何相关背景的情况下，我对Haskell的世界感到很好奇。原因是我遇到了一个难题，我正在尝试解决它，它似乎是基于haskell代码。我相信我要找的是一个整数。

我尝试做的事情如下

let a = \x -> x (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> y (y z)) (\x -> y (y (y (y (y (y (y x))))))) z) (\x -> y (y (y (y (y (y (y (y (y x))))))))) z) y (y z)) (\x -> y (y (y (y x)))) z) y (y z)) (\x -> y (y (y (y x)))) z) (\x -> y (y (y (y (y x))))) z) y (y z)) (\x -> y (y (y (y (y (y (y (y x)))))))) z) (\x -> y (y (y (y (y (y (y (y x)))))))) z) (\x -> y (y (y (y (y (y (y (y x)))))))) z) (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> y (y z)) (\x -> y (y (y (y (y (y (y (y (y x))))))))) z) y (y z)) (\x -> y (y (y (y (y x))))) z) (\x -> y (y (y (y (y (y x)))))) z) y (y z)) (\x -> y (y x)) z) (\x -> y (y (y (y (y (y x)))))) z)

a (1+) 0

这将返回以下错误消息

<interactive>:1:4:
No instance for (Num
                   (((t20 -> t20) -> t20 -> t20) -> (t20 -> t20) -> t20 -> t20))
  arising from the literal `1'
Possible fix:
  add an instance declaration for
  (Num (((t20 -> t20) -> t20 -> t20) -> (t20 -> t20) -> t20 -> t20))
In the first argument of `(+)', namely `1'
In the first argument of `a', namely `(1 +)'
In the expression: a (1 +) 0

<interactive>:1:8:
No instance for (Num (t20 -> t20))
  arising from the literal `0'
Possible fix: add an instance declaration for (Num (t20 -> t20))
In the second argument of `a', namely `0'
In the expression: a (1 +) 0
In an equation for `it': it = a (1 +) 0

简单的问题--我需要做什么才能让它工作？

请记住，目前我对此知之甚少。我将非常感谢任何人给我的任何帮助！

编辑：

我确实得到了一个类似的表达：

let x = \s z -> ((\s z -> ((\s z -> ((\s z -> ((\s z -> (((\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s . s) z)) s z) s) . ((\s z -> s z) s)) z) . (\s z -> (((\s z -> ((\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s) z)) s z) . (\s z -> (s . s . s) z)) s z) s) . ((\s z -> s z) s)) z)) s z) . (\s z -> (((\s z -> ((\s z -> (s . s) z) (\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s) z)) s z)) s z) s) . ((\s z -> (s . s . s) z) s)) z)) s z) . (\s z -> (((\s z -> ((\s z -> (s . s) z) (\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s) z)) s z)) s z) s) . ((\s z -> (((\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s . s) z)) s z) s) . ((\s z -> s z) s)) z) s)) z)) s z) . (\s z -> (((\s z -> ((\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s . s) z)) s z) . (\s z -> (((\s z -> ((\s z -> ((\s z -> (s . s) z) . (\s z -> (s . s) z)) s z) . (\s z -> (s . s . s) z)) s z) s) . ((\s z -> s z) s)) z)) s z) s) . ((\s z -> s z) s)) z)) s z

x (1+) 0

它返回整数3141593

Answer 1

好的，让我们把它分解成更小的部分。事实上，这个表达式就是太多的线噪声。

首先，请注意有一堆类似的东西:用于不同数量的y应用程序的(\x -> y (y (y (y (y (y x))))))。因此，让我们将其抽象出来：

(^^) :: (a -> a) -> Int -> (a -> a)
y ^^ 0 = id
y ^^ n = y . (y ^^ (n - 1))

所以(\x -> y (y (y (y (y (y x))))))就是y ^^ 6。

这开始看起来像这样：

let a = \x -> x 
              (\y z -> 
                (\y z -> 
                  (\y z -> 
                    (\y z -> 
                      (\y z -> 
                        (\y z -> 
                          (\y z -> 
                            (\y z -> 
                              (\y z -> 
                                (\y z -> 
                                  (\y z -> 
                                    (\y z -> y (y z)) (y ^^ 7) z) 
                                  (y ^^ 9) z) 
                                y (y z)) 
                              (y ^^ 4) z) 
                            y (y z)) 
                          (y ^^ 4) z) 
                        (y ^^ 5) z) 
                      y (y z)) 
                    (y ^^ 8) z) 
                  (y ^^ 8) z) 
                (y ^^ 8) z) 
              (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> (\y z -> y (y z)) (y ^^ 9) z) y (y z)) (y ^^ 5) z) (y ^^ 6) z) y (y z)) (y ^^ 2) z) (y ^^ 6) z)

仍然不是很好，但让我们把注意力集中在这个巨大楔子的尖端

(\y z -> y (y z)) (y ^^ 7) z 

(\y z -> y (y z))只是(\y -> y ^^ 2)，所以让我们把它放在：

(\y -> y ^^ 2) (y ^^ 7) z 

使用替换，这给了我们

((y ^^ 7) ^^ 2) z

这是我展示我预知的命名技巧的地方，并做出令人震惊的(但却是真的！)声称(y ^^ 7) ^^ 2 == (y ^^ 14)。也就是说，在英语中，如果我们连续调用y 7次，连续调用2次，这与连续调用y 14次相同。

所以现在我们只剩下

(y ^^ 14) z

如果我们后退一点，那就是

(\y z -> (y ^^ 14) z) (y ^^ 9) z

，它与

(\y -> y ^^ 14) (y ^^ 9) z

，它与

((y ^^ 9) ^^ 14) z

，它与

(y ^^ 126) z

以此类推。

偶尔你会遇到像这样的情况

(\y -> y ^^ n) y (y z)

这真的就是

(y ^^ n) (y z)

或

(y ^^ (n+1)) z

无论如何，您可以使用这些方法继续简化代码，直到您获得

let a = \x -> x (\y -> y ^^ 2652672) (\y -> y ^^ 6852)

或者诸如此类的事情，我可能在某一时刻数错了y。

但这就是最简单的方法了。

现在，您可以传递一个a函数，如：a $ \f g -> f (+1) 0 + g (+1) 0，它将2652672次加1到0，再加1到06852次，并对结果求和。由于我们目前已经实现了(^^)，这将需要很长时间才能得到2659524。

Answer 2

a的类型相当复杂，并且您的参数不适合该函数：

Prelude> :t a
a :: (((t1 -> t1) -> t1 -> t1) -> ((t2 -> t2) -> t2 -> t2) -> t)
     -> t

由于(1+) :: Num a => a -> a的类型不是(((t1 -> t1) -> t1 -> t1) -> ((t2 -> t2) -> t2 -> t2) -> t)形式，因此它不是a的有效参数。

很难说问题是从哪里来的，因为不清楚这个表达式应该做什么，也不清楚它是如何推导出来的。也许一些括号是错误的，或者是嵌套的lambda表达式的参数名称隐藏了外部lambda的参数，从而导致了这个问题。