时间戳

首页 > 解决方案 > 如何从类型签名中实现功能？

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

问题描述

我在 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)最终返回aand c。

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

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

标签： functionhaskelltypesfunctional-programmingimplementation

解决方案

你有一些误解：

我知道它foo需要一个函数(a -> (a,b))并返回a一个包含b.

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

并bar接受一个函数，该函数(b -> c)返回一个函数，该函数(a -> b -> c)最终返回aand c。

同样在这里。给定g :: a -> b，bar返回一个函数bar g :: (a -> b -> c) -> a -> c。反过来，这个函数给定一个 function 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 = ....

我们这里没有太多的自由选择。虽然，有更多的方法来获得更多的类型值b，对于foo。a我们可以在(a,b) = g x的更多应用中使用它，而不是忽略它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). 拥有最一般的定义可能是最好的。

推荐阅读