通用容器转换？如果从可折叠到替代？

Question

对于 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)

泛化所有函数并使用此类比创建新实例实际上是个好主意，尤其是对于列表操作？

编辑：我特别担心模棱两可的 return 类型。对于普通的列表操作， return 类型可以从其参数类型中推导出来。但是 "universal" 版本不是，因为必须明确指定 return 类型。这个问题严重到足以认为这个类比是危险的吗？（或者还有其他问题？）

编辑 2：如果我准确理解 foldl' 的行为，则通用 splitAt（如上所示）的时间复杂度必须为 Θ(length xs)，因为 foldl' 对每个元素都是严格的，对吧？如果是，那一定是个问题，因为它不如普通版的 Θ(min n (length xs)).

Answer 1

使函数在理论上尽可能多态并不总是一个好主意，尤其是函数参数。根据经验：使 function results 尽可能多态。（通常，参数将已经包含一些在结果中使用的类型变量。）只有当你有特殊原因时，也给参数额外的多态性。

原因是：如果所有东西 都是多态的，编译器没有关于选择什么具体类型的提示。多态 results/values 通常是可以的，因为它们通常会直接或间接绑定到一些具有显式签名的顶级定义，但多态 arguments 通常只会被填充文字（数字文字在 Haskell 中是多态的，strings/lists 也可以）或其他多态值，因此您最终不得不输入大量显式本地签名，这往往比拥有更尴尬偶尔使用显式转换函数，因为某些东西不够多态。

Foldable->Alternative 的这个想法特别有另一个问题，即 Alternative class 是相当不受欢迎的，没有非常坚实的数学支持。它基本上是应用仿函数的 class，每个实例化都会产生一个 Monoid。嗯，这也可以直接表达，要求 Monoid 本身。 “通用容器转换函数”因此已经存在，它是<a href="http://hackage.haskell.org/package/base-4.10.1.0/docs/Data-Foldable.html#v:foldMap" rel="nofollow noreferrer">foldMap</a> pure.

通用容器转换？如果从可折叠到替代？

Universal container conversion? if from Foldable to Alternative?

haskell

containers

applicative

foldable

alternative-functor