gpt4 book ai didi

haskell - 基于右 Kan 扩展的列表

转载 作者:行者123 更新时间:2023-12-03 21:37:50 25 4
gpt4 key购买 nike

在``Kan Extensions for Program Optimisation '' Ralf Hinze 的 List 类型的定义是基于从 monoids 的范畴沿自身的遗忘仿函数的右 Kan 扩展(第 7.4 节)。论文给出了 Haskell 的实现如下:

newtype List a = Abstr {
apply :: forall z . (Monoid z) => (a -> z) -> z
}

我能够定义通常的 nil 和 cons 构造函数:
nil :: List a
nil = Abstr (\f -> mempty)

cons :: a -> List a -> List a
cons x (Abstr app) = Abstr (\f -> mappend (f x) (app f))

使用 Maybe 仿函数的 Monoid 类的以下实例,我设法定义了 head 函数:
instance Monoid (Maybe a) where
mempty = Nothing
mappend Nothing m = m
mappend (Just a) m = Just a

head :: List a -> Maybe a
head (Abstr app) = app Just

问题 : 如何定义尾函数?

最佳答案

这是一次实现头部和尾部的相当原则的解决方案(full gist):

首先,我们知道如何追加列表(稍后会有用):

append :: List a -> List a -> List a
append (Abstr xs) (Abstr ys) = Abstr (\ f -> xs f <> ys f)

那么我们引入一个新类型 Split我们将使用它来检测 List是否为空(如果它不为空,则获取头部和尾部):
newtype Split a = Split { outSplit :: Maybe (a, List a) }

这种新类型形成了一个幺半群:我们确实知道如何附加两个列表。
instance Monoid (Split a) where
mempty = Split Nothing
mappend (Split Nothing) (Split nns) = Split nns
mappend (Split mms) (Split Nothing) = Split mms
mappend (Split (Just (m, ms))) (Split (Just (n, ns))) =
Split $ Just (m, append ms (cons n ns))

这意味着我们可以从 List a 获得一个函数至 Split a使用 List aapply :
split :: List a -> Split a
split xs = apply xs $ \ a -> Split $ Just (a, nil)
headtail终于可以从 split 中简单地推导出来:
head :: List a -> Maybe a
head = fmap fst . outSplit . split

tail :: List a -> Maybe (List a)
tail = fmap snd . outSplit . split

关于haskell - 基于右 Kan 扩展的列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27381133/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com