function - 如何从类型签名实现功能？

Question

我在 Haskell 中有以下两种类型签名:

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

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

我想编写这两个函数的具体实现，但我真的很难理解从哪里开始。

我知道 foo 接受一个函数 (a -> (a,b)) 并返回 a 和一个包含 b.

bar 接受一个函数 (b -> c) 返回一个函数 (a -> b -> c) 最后返回 a 和 c。

谁能给我一个具体实现的例子？

我怎么知道从哪里开始这样的事情以及定义左侧的内容？

Answer 1

你的理解有误:

I understand that foo takes a function (a -> (a,b)) and returns a and a list containing b.

不，它不返回a。除了该函数之外，它还期望它作为另一个参数。

And bar takes a function (b -> c) which returns a function (a -> b -> c) which finally returns a and c.

这里也一样。给定 g::a -> b，bar 返回函数 bar g::(a -> b -> c) -> a -> c。反过来，给定函数 h::(a -> b -> c)，此函数返回 a -> c 类型的函数。就这样。

---

这就像玩拼图一样:

foo :: (a -> (a,b)) -> a -> [b]
--   g   :: a -> (a,b)
--     x :: a
--   g x ::      (a,b)
foo g x = [b]  where
  (a,b) = g x

bar :: (a -> b) -> (a -> b -> c) -> a -> c
--   g   :: a -> b
--     x :: a
--   g x ::      b
--   h   :: a -> b -> c
--   h x ::      b -> c
--   h x (g x)     :: c
bar g h x = c  where
  c = ....

我们在这里没有多少自由选择。虽然，对于 foo，有更多方法可以获取更多 b 类型的值。而不是忽略(a,b) = g x中的那个a，我们可以在g的更多应用中使用它，所以其实有很多那里有更多的可能性，比如

foo2 :: (a -> (a,b)) -> a -> [b]
foo2 g x = [b1,b2]  where
  (a1,b1) = g x
  (a2,b2) = g a1

还有更多。尽管如此，类型还是指导了可能的实现。根据类型，foo 甚至可以在其实现中使用 foo:

foo3 :: (a -> (a,b)) -> a -> [b]
foo3 g x = b : bs  where
  (a,b) = g x
  bs = ...

现在，有了这个实现，前两个变成了它的特例:foo g x === take 1 (foo3 g x) 和 foo2 g x === take 2 (foo3 g x )。拥有最一般的定义可能是最好的。