据我明白,从Haskell的递归数据类型对应于endofunctors的初始代数从Hask类别[ 1,2 ].例如:
data Nat = Zero | Succ Nat对应于endofunctor的初始代数F(-) = 1 + (-).data List a = Nil | Cons a (List a)对应于endofunctor的初始代数F(A, -) = 1 + A × (-).但是,我不清楚对应玫瑰树的endofunctor应该是什么:
data Rose a = Node a (List (Rose a))
令我困惑的是,有两个递归:一个用于玫瑰树,另一个用于列表.根据我的计算,我会得到以下仿函数,但它似乎不正确:
F(A, •, -) = A × (1 + (-) × (•))
或者,可以将玫瑰树定义为相互递归的数据类型:
data Rose a = Node a (Forest a)
type Forest a = List (Rose …recursion haskell algebra algebraic-data-types category-theory
Hask通常被认为是对象是类型的类别,而态射是函数.然而,我看到康纳尔麦克布莱德(@pigworker)警告反对使用Hask多次(1,2,3):
我会劝阻谈论"Hask类别",因为它潜意识地阻止你在Haskell编程中寻找其他分类结构.
注意,我不喜欢使用"Hask"作为"Haskell类型和函数类别"的名称:我担心将一个类别标记为Haskell类别会产生令人遗憾的副作用,使我们对其他分类结构的财富感到盲目在Haskell编程中.这是一个陷阱.
我希望人们不要称它为"哈斯克",它可能会限制想象力.
我们在Haskell中可以看到哪些其他类别？
在他的一个答案中,他触及了其中的一些想法,但我想知道是否有人可以扩展它; 我想知道是否还有更多的例子.
[...]各地潜伏着大量的分类结构,当然有更多类别的分类结构(可能但不一定).我特别喜欢索引族集之间的仿函数.
monad的各种实例模拟不同类型的效果:例如,Maybe模型偏好,List非确定性,Reader只读状态.我想知道是否对流数据类型(或无限列表或共同列表)的monad实例有这样一个直观的解释data Stream a = Cons a (Stream a)(参见下面的monad实例定义).我在几个 不同的 场合偶然发现了流monad ,我想更好地了解它的用途.
data Stream a = Cons a (Stream a)
instance Functor Stream where
fmap f (Cons x xs) = Cons (f x) (fmap f xs)
instance Applicative Stream where
pure a = Cons a (pure a)
(Cons f fs) <*> (Cons a as) = Cons (f a) (fs <*> as)
instance Monad Stream where
xs >>= f = diag (fmap …如果我理解正确的话,我们可以将归纳数据类型建模为初始F-代数和共感应数据类型作为最终的F-余代数(对于适当的endofunctor F)[ 1 ].据我所知,根据Lambek的引理,初始代数(和最终的余代数)是同构的不动点解T ? F T,但我不明白为什么初始代数是最不固定的点,而最终的代数是最大的固定点.(同构现象T ? F T有明显的解决方案吗？)
另外,我还不清楚类型理论中如何定义归纳和共感数据类型.是否有关于此主题的推荐资源,以及它们与类别理论的关系？
谢谢!
我正在阅读Jeremy Gibbons关于折纸编程的文章,我坚持练习3.7,要求读者证明列表的融合法展开:
Run Code Online (Sandbox Code Playgroud)unfoldL p f g . h = unfoldL p' f' g'如果
Run Code Online (Sandbox Code Playgroud)p . h = p' f . h = f' g . h = h . g'
unfoldL列表展开的功能定义如下:
unfoldL :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> List a
unfoldL p f g b = if p b then Nil else Cons (f b) (unfoldL p f g (g b))
这是我目前尝试的证据:
(unfoldL p f …Conor McBride(pigworker)的答案讨论了Applicative也是容器的算子(由一组形状和一系列位置给出的数据类型).除其他外,他提到:
<*>.我想知道是否可以在分类设置中进行类似的分析,并且我是否可以使用类别理论得出相同的结论(主要是因为我觉得类别理论比依赖类型理论更容易).
我知道仿Applicative函数是monoidal仿函数(从(Set, ×, 1)到(Set, ×, 1)),我相信容器可以被视为在列表上形状的仿函数(如这里或这里所建议的) - 但我对这个概念或这个断言不太满意.这是考虑应用容器的正确方法吗？作为整体列表上的幺半体仿函数？
PS:如果您认为stackoverflow不适合提出这类问题,请告诉我.
list当应用于嵌套生成器时,函数如何表现？在下面的代码片段中,我发现行为相当令人费解:似乎list消耗了大多数嵌套生成器,而最后一个仍保留一个元素:
>>> from itertools import groupby
>>> xs = [1, 2, 2, 3, 3]
>>> for k, g in list(groupby(xs)):
... print(k, list(g))
1 []
2 []
3 [3]
我使用Store comonad 编写了Conway的生命游戏的简单实现(参见下面的代码).我的问题是,从第五次迭代开始,网格生成明显变慢.我的问题与我使用Store comonad的事实有关吗？还是我犯了一个明显的错误？据我所知,其他的实现,这是基于拉链comonad,是有效的.
import Control.Comonad
data Store s a = Store (s -> a) s
instance Functor (Store s) where
fmap f (Store g s) = Store (f . g) s
instance Comonad (Store s) where
extract (Store f a) = f a
duplicate (Store f s) = Store (Store f) s
type Pos = (Int, Int)
seed :: Store Pos Bool
seed = Store g (0, 0)
where
g ( 0, 1) …考虑将列表连接实现为左侧折叠,即foldl (++) [].在惰性求值语言中,例如Haskell,这种实现的复杂性是什么？我理解,在严格的语言中,表现是元素总数的二次方,但是当涉及懒惰时会发生什么？
我试图用手工评估表达式([1,2,3] ++ [4,5,6]) ++ [7,8,9](对应于foldl (++) [] [[1,2,3], [4,5,6], [7,8,9]]),似乎我们只遍历每个元素一次,但我不确定我的推理是否正确:
([1,2,3] ++ [4,5,6]) ++ [7,8,9]
= { rewrite expression in prefix notation }
(++) ((++) [1,2,3] [4,5,6]) [7,8,9]
= { the first (++) operation needs to pattern match on its first argument; so it evaluates the first argument, which pattern matches on [1,2,3] }
(++) (case [1,2,3] of {[] -> [4,5,6]; x:xs' -> x:(++) xs' [4,5,6]}) [7,8,9]
= { x = …