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

シード関数とリストを取り、シード関数をリストの最初の要素に適用し、それによって返された関数をリストの 2 番目の要素に適用することによって作成されたリストを返します。

これは機能しますが、これをもう少し便利なことに使用する過程で、自分以外の関数を返す関数が基本単位であることが多くあることに気付きました。そして、自分自身を返す関数を明示的に宣言することは、やや退屈になりつつありました。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は単なる特殊なケースであることがすぐにわかります。適切なインフラストラクチャが整っていれば、 のリストを作成することもできbます。したがって、型を一般化しようとしRます。

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

この種の構造が a と呼ばれているのを見たCircuitことがありますが、これはたまたま本格的なarrowです。アローは関数の概念を一般化したものであり、モナドよりもさらに強力な構造です。圏論の背景を理解しているふりをすることはできませんが、彼らと一緒に遊ぶのは間違いなく興味深いものです。たとえば、自明な変換は次の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

あなたが持っているのはストリームの簡略化されたバージョンのようです。つまり、値の無限の流れの表現です。これをモナドとして簡単に定義できるとは思いません。なぜなら、シードに要素と同じ型を使用しているため、定義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 でも同様に機能します。ライブラリ内の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 に答える