7

我正在使用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类似物而变得贪婪？

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

4

3 回答 3

7

作为一个高级考虑，我会说你的类型代表一个有状态的流转换器。这里有点令人困惑的是您的类型定义为

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]

如果我们尝试推广流转换器的这个想法，我们很快就会意识到我们将 s 列表转换为as 列表的a情况只是一种特殊情况。有了适当的基础设施，我们也可以生成一个bs 列表。所以我们尝试泛化类型R：

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

我见过这种结构被称为 a Circuit，它恰好是一个成熟的箭头。箭头是函数概念的概括，是比单子更强大的构造。我不能假装理解范畴理论的背景，但和他们一起玩肯定很有趣。例如，简单的转换就是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)]
于 2013-02-22T01:22:57.737 回答
1

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

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

这将允许您定义 aFunctor和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

请注意，这仅在将其视为集合时才遵守 Monad 定律，因为它不保留元素顺序。

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

于 2013-02-22T01:14:15.703 回答
0

我没有太多要补充的，只是要注意你的cascade函数可以写成左折叠（因此也可以写成右折叠，尽管我没有进行转换。）

cascade f = reverse . fst . foldl func ([], f)
  where
    func (rs,g) s = let R (r,h) = g s in (r:rs,h)
于 2013-02-21T23:55:28.573 回答