haskell - 有没有一种优雅的方式让函数返回相同类型的函数(在元组中)

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而变得贪婪类似物？

(顺便说一句，除此之外，“返回自身的函数”或“递归数据结构(函数)”，我不太确定这种模式叫什么，并且很难对其进行有效的研究——如果任何人都可以给我这个模式的名称(如果它确实有一个)，仅此一项就非常有帮助)

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 的列表s 只是一个特例。有了适当的基础设施，我们也可以生成 b 的列表。 s。所以我们尝试泛化类型 R :

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

我见过这种结构被称为 Circuit , 这恰好是一个成熟的 arrow .箭头是函数概念的概括，是比单子(monad)更强大的构造。我不能假装理解范畴理论的背景，但和他们一起玩肯定很有趣。例如，简单的转换只是 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)]