在 Haskell 中定义满足类型的函数

Question

类型

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

考虑到我要创建一个满足此类型的函数的

...我知道 foo xy = y（\ z - ＆gt; x）满足此类型，如：类型在GHCI中，但是我该如何手动或逐步执行此最终功能？

我也知道 foo2 fg = \ x-＆gt; f（gx）也会满足 foo2 ::（a - ＆gt; b） - ＆gt; （c - ＆gt; a） - ＆gt; c - ＆gt; B ，但也不知道如何获得此功能。

Answer 1

这只是将拼图的匹配部分融合在一起的问题。相同的零件匹配。 foo 的类型意味着它具有两个参数：

foo :: a -> ((b -> a) -> c) -> c
--     a    f

foo a f     =     c
 -- a       :: a
 --   f g   ::    c
 --     g b :: a
  where
  c = f g         -- produce a c-type value
  g       b =  a  -- define g to produce
                  --   the value a

f 我们给出了，但是 g 我们必须发明，以便它返回 a ;幸运的是，我们已经给出了一个 a ：

-- f :: ((b -> a) -> c)
--       g

-- g ::   b -> a

a 作为 foo 的参数和 b 只是 g 的未使用参数。

接下来，我们可以使用以下事实来替代和简化：

p :: q -> r
p    q =  r...

与写作相同：

p :: q -> r
p = \q -> r...

在其中使用 r ... 来指示其类型为 r 的表达式。

另外， s - ＆gt; t - ＆gt; r 与 s-＆gt; （t - ＆gt; r），因为同样，

h :: s ->   t -> r
h    s      t =  r...
h    s =  (\t -> r...)
h = \s -> (\t -> r...)

都表达了同一件事。

您的第二个问题可以以相同的方式解决。

x :: a ＆nbsp;表示“值＆nbsp; x ＆nbsp;有类型＆nbsp; a a ” ＆nbsp;的意思是“价值＆nbsp; code> a ＆nbsp;具有类型＆nbsp; a '”。可以在两个不同的角色中使用相同的名称 a ＆nbsp;当您习惯它时，它实际上可能是一个有用的助记符。

另请参见。

Answer 2

下划线 _ ，或一个以下划线（例如 _ What What What ）开始的未定义名称，GHC将其视为您要填充的“孔”。您可以使用此信息。询问编译器期望什么类型，这可能有助于弄清楚如何迭代填充程序。值得庆幸的是，在这种情况下，它非常有用，因此我可以轻松地在GHCI中逐步进行（带有＆gt; 表示提示）。我们从孔 foo = _ 开始，

> foo :: a -> ((b -> a) -> c) -> c; foo = _

然后收到一条消息，说找到孔：_ :: a-＆gt; （（b - ＆gt; a） - ＆gt; c） - ＆gt; C 。 GHC建议 foo :: a - ＆gt; （（b - ＆gt; a） - ＆gt; c） - ＆gt; C 是填充孔的有效方法，实际上 foo = foo 是合法的，它不是我们要寻找的答案，因为它代表了一个无限的环路。

取而代之的是，我们可以查看类型并将其从上层向下分解为部分。我们从函数类型（ - ＆gt; ）开始，其输入为 a 并且其输出为（（b - ＆gt; a） - ＆gt; c） - ＆gt; C 。我们可以使用lambda表达式制作功能值，为 a 值发明名称，例如 x ，并为身体添加另一个漏洞：

> foo :: a -> ((b -> a) -> c) -> c; foo = \ x -> _

…
    • Found hole: _ :: ((b -> a) -> c) -> c
…

它现在提到我们有 X :: A 除 foo 之外，还可以使用，但这还不够，因此接下来我们可以分开（（b-＆gt） a） - ＆gt; c 进入其输入（（（b - ＆gt; a） - ＆gt; c）和输出 c 。 （从现在开始，为了简洁起见，我还会跳过重复 foo 的类型签名。）

> foo :: …; foo = \ x -> \ f -> _

…
    • Found hole: _ :: c
…

我们无法将类型变量 c 进一步分开，并且我们知道我们需要构成类型 c 的值，因此我们可以查看我们的可用内容：

• f ::（b - ＆gt; a） - ＆gt; c
• x :: a
• foo :: a - ＆gt; （（b - ＆gt; a） - ＆gt; c） - ＆gt; c

，我们的选项是：

1. 递归致电 foo

2. 呼叫 f

＃1很快就会使我们陷入我们所处的相同情况，因此＃2就是剩下的。 f 期望类型的值 b-＆gt; 作为参数：

> foo :: …; foo = \ x -> \ f -> f _

…
    • Found hole: _ :: b -> a
…

因此，我们可以再次编写一个lambda：

> foo :: …; foo = \ x -> \ f -> f (\ y -> _)

…
    • Found hole: _ :: a
…

我们产生未知类型 a 的唯一方法是使用值 x :: a x :: a < /code>我们已经获得了，因此最终结果是：

foo = \ x -> \ f -> f (\ y -> x)

可以用与您的问题完全相同的形式写入，使用少量句法糖，以及可变名称的几个不同选择：

foo     = \ x -> \ f -> f (\ y -> x)
foo x   =        \ f -> f (\ y -> x)
foo x f =               f (\ y -> x)

foo x y =               y (\ z -> x)

Answer 3

问题 1

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

表示 foo 必须接受一个 a 和一个类型为 (b -> a) ->; 的函数。 c 并以某种方式产生一个 c.

foo a function = c

其中a::a 和function::(b -> a) -> c
但是我们从哪里可以得到c呢？

好消息：function 为我们创建了 c。

让我们使用它。 函数::(b->a) -> c 因此，如果我们给它一个 (b->a)，我们就可以得到一个 c。

因此，我们需要首先创建一个辅助函数，它接受 bs 并给我们 as：

foo a function = 
   let helper b = a

很好！我已经有一个 a 所以我可以使用它。我们只需要将我们刚刚创建的 helper 交给 function 即可：

foo :: a -> ((b -> a) -> c) -> c
foo a function = 
   let helper b = a 
   in function helper

现在请注意，helper 忽略了它的输入，因此我们可以编写

foo :: a -> ((b -> a) -> c) -> c
foo a function = 
   let helper _ = a 
   in function helper

我们可以使用 lambda helper 的符号：

foo :: a -> ((b -> a) -> c) -> c
foo a function = 
   let helper = \_ -> a 
   in function helper

但现在我们可以只写 (\_ -> a) 而不是 helper：

foo :: a -> ((b -> a) -> c) -> c
foo a function = 
   function (\_ -> a)

最后，让我们将 function 缩写为 f：

foo :: a -> ((b -> a) -> c) -> c
foo a f = f (\_ -> a)

问题2

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

好的，这次我们需要制作一个b。我们给出了一个 c 和几个函数，用于将 as 转换为 bs，将 cs 转换为as：

foo2 :: (a -> b) -> (c -> a) -> c -> b
foo2 
   make_b_from_a 
   make_a_from_c 
   c 
      = b

嗯，唯一能给我们 b 的是 make_b_from_a：

foo2 :: (a -> b) -> (c -> a) -> c -> b
foo2 
   make_b_from_a 
   make_a_from_c 
   c 
      = make_b_from_a a

但现在我们需要一个 a >，但我们可以使用 make_a_from_c为此，我们已经有了一个 c：

foo2 :: (a -> b) -> (c -> a) -> c -> b
foo2 
   make_b_from_a 
   make_a_from_c 
   c 
      = make_b_from_a (make_a_from_c c)

让我们缩短名称。我将把 (c->a) 称为 f 因为我们在另一个之前使用它，我将其称为 g：

foo2 :: (a -> b) -> (c -> a) -> c -> b
foo2 g f c = g (f c) 

我们可以使用 lambda 获取最后一个参数：

foo2 :: (a -> b) -> (c -> a) -> c -> b
foo2 g f = \c -> g (f c)