代码之家 › 专栏 › 技术社区 › Dannyu NDos AJF

通用容器转换?是否从可折叠到备用?

alternative-functor foldable applicative containers haskell

2

Dannyu NDos AJF · 技术社区 · 7 年前

对于 instance Alternative [] , (<|>) = (++) . 所以我认为 (<|>) 作为某种类型的拼接器,导致看起来几乎通用的容器转换器:

-- (<|>) = generalization of (++)

(<|) :: Alternative f => x -> f x -> f x
x <| xs = pure x <|> xs

conv :: (Foldable t, Alternative f) => t x -> f x
conv = foldr (<|) empty

事实上,我能够概括 全部的 功能来自 Data.List ,以下是一些:

-- fmap = generalization of map

reverse :: (Foldable t, Alternative f) => t a -> f a
reverse = getAlt . getDual . foldMap (Dual . Alt . pure)

-- asum = generalization of concat

asumMap :: (Foldable t, Alternative f) => (a -> f b) -> t a -> f b -- generalization of concatMap
asumMap f = getAlt . foldMap (Alt . f)

splitAt :: (Foldable t, Alternative f, Alternative g) => Int -> t a -> (f a, g a)
splitAt n xs = let (_,fs,gs) = foldl' (\(i,z1,z2) x -> if 0 < i then (i-1,z1 . (x <|),z2) else (0,z1,z2 . (x <|))) (n,id,id) xs in (fs empty,gs empty)

此外,这种类比还产生了一些有趣的新实例,例如用于函子和的工作应用函子( Data.Functor.Sum ):

instance (Foldable f, Applicative f, Alternative g) => Applicative (Sum f g) where
    pure = InL . pure
    InL f <*> InL x = InL (f <*> x)
    InL f <*> InR x = InR (conv f <*> x)
    InR f <*> InL x = InR (f <*> conv x)
    InR f <*> InR x = InR (f <*> x)

instance (Foldable f, Applicative f, Alternative g) => Alternative (Sum f g) where
    empty = InR empty
    InL x <|> _ = InL x
    InR _ <|> InL y = InL y
    InR x <|> InR y = InR (x <|> y)

概括一下真的是个好主意吗 全部的 函数并使用这种类比创建新实例,尤其是列表操作?

编辑:我特别关注不明确的返回类型。对于普通的列表操作,返回类型可以从其参数类型中推断出来。但“通用”版本不是,因为必须显式指定返回类型。这个问题是否严重到足以将这个类比视为危险的程度?(或者是否有其他问题?)

编辑2:如果我了解 foldl' 没错,宇宙的时间复杂性 splitAt (如上所示)必须 Î(length xs) 像 福尔德 对每个元素都很严格,对吗?如果是,那一定是个问题,因为它不如常规版本 Î(min n (length xs)) .

1 回复 | 直到 3 年前

1

3

leftaroundabout 7 年前

在理论上尽可能使函数具有多态性并不总是一个好主意,尤其是 函数参数 . 经验法则:生成函数后果尽可能多态。(通常情况下,参数已经包含结果中使用的某些类型变量。)只有当你有一个特殊的原因时,还要给参数额外的多态性。

原因是:如果 每件事 是多态的,编译器没有关于选择什么具体类型的提示。多态结果/值通常是可以的,因为这些结果/值通常直接或间接地绑定到具有显式签名但多态的顶级定义论据通常只会填充文字(数字文字在Haskell中是多态的,字符串/列表也可以是多态的)或其他多态值,因此最终必须键入大量显式本地签名,这往往比偶尔插入显式转换函数更为尴尬,因为 多态性不够 .

这个想法 Foldable->Alternative 特别是还有另一个问题 Alternative 课堂上没有非常坚实的数学基础,因此很不受欢迎。它基本上是一类应用程序函子,对于每个实例化,它都会产生 Monoid . 也可以通过要求 幺半群 它本身因此,“通用容器转换函数”已经存在,它是 foldMap pure .