ファンクションに同じ型（ファンクション）のファンクションを返すようにする方法はありますか？

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 

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

しかしこれをやや便利なものに使う過程で、私は基本単位が自分自身以外の関数を返す関数であることに気付きました。明示的に自分自身を返す関数を宣言することはやや面倒になっていた。私はむしろMonadのreturn関数のようなものを使うことができるだろうが、bindがこれらの型の関数に対して何をするのか分からない。最初の場所。モナドにこれを押し込もしようとすると

は私が何をやっていたかどうかについて教えて心配始めに便利だったので、簡単に言えば、私が知りたいことは次のとおりです。

• は私がやっているです悪いこと？もしそうでなければ、
• 私は前にやったことがありますか？私はここで車輪を再発明していますか？そうでない場合は
• これを行うにはエレガントな方法がありますか、すでに私はこれに達しており、returnアナログを欲しいと貪欲にしていますか？

（ちなみに、ほかに、「themeselvesを返す関数」または「機能の再帰的なデータ構造（）」、私はこの種のパターンが呼び出され、かつ効果的な研究をやろうとしてきたものを、非常にわからないんだけどそれは難しい - もし誰かが私にこのパターンの名前を与えることができれば（実際にそれがあれば）、それだけで非常に役に立ちます）

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のリストを作成することもできます。私は本格的arrowであることを起こるCircuitと呼ばれているこの種の構造を、見てきました

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

：だから我々はタイプRを一般化してみてください。矢印は関数の概念の一般化であり、モナドよりもさらに強力な構造です。カテゴリの理論的背景を理解するふりをすることはできませんが、実際にそれらと遊ぶのは間違いありません。例えば、些細な変換はちょうど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)] 

Answer 2

私はあなたのcascade関数左折として書くことができます（したがって、私は変換を行っていませんが、右折としても書くことができます）。

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

Answer 3

あなたが持っているものはストリームの簡略版です。つまり、 と言うと、無限の値のストリームの表現です。私はあなたの要素のための としてあなたの子孫のために同じタイプを使用するので、あなたが 簡単にあなたが がfmapに提供する機能を反転させる必要があるだろうと思われる（難しいfmapを定義せた、モナドとしてこれを定義することができるとは思いませんそうすることができるように シードを回復する）。あなたは、これは、このことだけを

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 

注意を次のようにFunctorとMonadインスタンスを定義することができますので、

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

のような要素型の独立したシードタイプ を作ることによって、このモナドを作ることができます 要素の順序を保持していないので、モナドの法則に従うと、セットと見なされます。ストリームモナドの

This説明 は、彼らが怠惰な方法で生成することができますので、Haskellの に同じようにうまく機能している、無限リストを使用しています。 vectorライブラリのStreamタイプの ドキュメントをチェックアウトすると、 より効率的なストリーム融合に使用できるように、より複雑なバージョンが見つかります。