有没有一种优雅的方法让函数返回相同类型的函数（以元组形式）？

Question

我正在使用Haskell实现一个涉及返回值和它们本身（或相同类型的函数）的模式。目前，我的实现方式如下：

newtype R a = R (a , a -> R a)

-- some toy functions to demonstrate    
alpha :: String -> R String
alpha str
    | str == reverse str = R (str , omega)
    | otherwise          = R (reverse str , alpha)

omega :: String -> R String
omega (s:t:r)
    | s == t    = R (s:t:r , alpha)
    | otherwise = R (s:s:t:r , omega)

这些函数的驱动力是一个叫做级联的函数：

cascade :: (a -> R a) -> [a] -> [a]
cascade _ [] = []
cascade f (l:ls) = el : cascade g ls where
    R (el , g) = f l

这是一个接受种子函数和列表的函数，返回通过将种子函数应用于列表的第一个元素，将该函数返回到列表的第二个元素等等创建的列表。

这个方法是有效的，但在使用它进行更有用的事情时，我注意到很多时候我拥有的基本单元是返回其他函数而不是自己的函数；显式声明一个函数返回自身变得有些乏味。我更愿意能够使用像Monad的“return”函数之类的东西，但是，我不知道对于这些类型的函数，“bind”会做什么，特别是因为我从未打算将它们与除了它们最初返回的函数之外的任何东西链接起来。

试图将此强行塞入Monad中开始让我担心我所做的是否有用，因此，简而言之，我想知道：

- 我所做的是件坏事吗？如果不是， - 我所做的事情以前已经完成/我正在重新发明轮子吗？如果不是， - 是否有一种优雅的方法来做这个，或者我已经达到了这个目标，只是贪心地想要某种“return”模拟？

（顺便说一下，除了“返回主题自己”或“递归数据结构（函数）”，我不太确定这种模式叫什么，这使得在其中进行有效研究变得困难——如果有人能为我给出这种模式的名称（如果它确实有一个），那就非常有帮助了）

- Lily

Answer 1

作为一个高级概念，我认为你的类型代表着一个有状态的流转换器。这里有一点令人困惑的是，你的类型被定义为：

newtype R a = R (a , a -> R a)

替代

newtype R a = R (a -> (R a, a))

在流媒体环境中，这样的说法更加自然，因为如果你还没有收到任何东西，通常不会“产生”任何东西。这样，您的函数类型也会更简单：

alpha, omage :: R String
cascade :: R a -> [a] -> [a]

如果我们试图概括流转换器的思想，很快就会意识到将一个 a 列表转换为另一个 a 列表只是一种特殊情况。有了适当的基础设施，我们同样可以生成一个 b 列表。因此，我们尝试概括类型 R：

newtype R a b = R (a -> (R a b, b))

我看到这种结构被称为电路，它恰好是一个完整的箭头。箭头是函数概念的泛化，比单子更强大的构造。我无法理解范畴论背景，但是玩弄它们肯定很有趣。例如，平凡变换只是Cat.id：

import Control.Category
import Control.Arrow
import Prelude hiding ((.), id)
import qualified Data.List as L

-- ... Definition of Circuit and instances

cascade :: Circuit a b -> [a] -> [b]
cascade cir = snd . L.mapAccumL unCircuit cir

--
ghci> cascade (Cat.id) [1,2,3,4] 
[1,2,3,4]

我们还可以通过将电路参数化为继续返回，来模拟状态：

countingCircuit :: (a -> b) -> Circuit a (Int, b)
countingCircuit f = cir 0
    where cir i = Circuit $ \x -> (cir (i+1), (i, f x))

--
ghci> cascade (countingCircuit (+5)) [10,3,2,11]
[(0,15),(1,8),(2,7),(3,16)]

我们的电路类型是范畴，这使我们有了一种很好的组合电路的方式：

ghci> cascade (countingCircuit (+5) . arr (*2)) [10,3,2,11]
[(0,25),(1,11),(2,9),(3,27)]

- Niklas B.

---

这看起来非常有趣 - 我肯定会阅读更多关于电路的内容。 - Lily

Answer 2

看起来你拥有的是一个简化版本的流。也就是说，它是无限值流的表示方式。我认为你很难将其定义为单子，因为你在种子和元素中使用了相同的类型，这使得定义fmap变得困难（似乎你需要反转提供给fmap的函数以便能够恢复种子）。你可以通过使种子类型独立于元素类型来使其成为单子，如下所示：

{-# LANGUAGE ExistentialQuantification #-}
data Stream a = forall s. Stream a s (s -> Stream a)

这将允许你如下定义Functor和Monad实例

unfold :: (b -> (a, b)) -> b -> Stream a
unfold f b = Stream a b' (unfold f)
    where (a, b') = f b

shead :: Stream a -> a
shead (Stream a _ _) = a

stail :: Stream a -> Stream a
stail (Stream _ b f) = f b

diag :: Stream (Stream a) -> Stream a
diag = unfold f
    where f str = (shead $ shead str, stail $ fmap stail str)

sjoin :: Stream (Stream a) -> Stream a
sjoin = diag

instance Functor Stream where
    fmap f (Stream a b g) = Stream (f a) b (fmap f . g)

instance Monad Stream where
    return   = unfold (\x -> (x, x))
    xs >>= f = diag $ fmap f xs

请注意，只有当被视为集合时，本文才遵守单子定律，因为它不保留元素顺序。

这个流单子的解释使用了无限列表，在Haskell中同样适用，因为它们可以以惰性方式生成。如果您查看vector库中Stream类型的文档，您会发现更复杂的版本，以便在有效的流融合中使用。这篇文章

- sabauma

Answer 3

我没有太多要补充的，除了指出你的cascade函数可以写成左折叠（因此也可以写成右折叠，尽管我还没有进行转换）。

cascade f = reverse . fst . foldl func ([], f)
  where
    func (rs,g) s = let R (r,h) = g s in (r:rs,h)

- Chris Taylor

---

谢谢你的提示 - 我知道我对最初的级联函数感到不满，但是一直拖延着修复它，因为还有其他更重要的事情要做。 - Lily