ラムダ関数としてサイクルを書く方法は？

Question

楽しみのためだけに、ここでcycleの私自身のバージョンです：

myCycle :: [a] -> [a] 
myCycle xs = xs ++ myCycle xs 

は右辺は、関数名myCycleとパラメータxsの両方を意味します。

それはが右側にmyCycleかxsに言及せずmyCycleを実装することは可能ですか？

myCycle = magicLambdaFunction 

Answer 1

は、それが右側にmyCycleかxsに言及せずmyCycleを実装することは可能ですか？

答えは「はい」と「いいえ」です（必ずしもその順番である必要はありません）。

他の人が固定小数点コンビネータについて言及しています。固定小数点コンビネータfix :: (a -> a) -> aをお持ちの場合は、Pubbyの回答へのコメントに記載されているように、myCycle = fix . (++)と書くことができます。

しかしfixの標準的な定義は、このです：fixの定義は、その定義の右側に左辺変数に言及することを含むこと

fix :: (a -> a) -> a 
fix f = let r = f r in r 

-- or alternatively, but less efficient: 
fix' f = f (fix' f) 

ノート（最初の定義でr、第2のものはfix'）。これまでに実際に行ってきたことは、問題をただちにfixにプッシュすることです。

注意する興味深いのは、Haskellのは、型付きラムダ計算に基づいているということである、と彼らは「ネイティブ」不動点コンビネータを発現しないできるように、良い技術的な理由のために、ほとんどの型付きラムダ計算は設計されています。これらの言語は、定点の計算を可能にする基本計算の「上」に特別な機能を追加すると、Turing-completeになります。たとえば、これらのいずれかは次のようになります。

1. 微積分のプリミティブとして「fix」を追加します。
2. 再帰的なデータ型を追加します（これはHaskellにあります;これはHaskellでfixを定義する別の方法です）。
3. 定義は、定義されている左側の識別子（Haskellにもあります）を参照できるようにします。

これは多くの理由、一方の固定点なしのラムダ計算は、多くのこのようなシステムでfix -lessプログラムが終了するように証明することができる別のこと、また論理一貫したプルーフシステムであることであるため、モジュールの有用なタイプであります。

---

EDIT：ここでは再帰的な型で書かれたfixです。今fix自体の定義は再帰的ではありませんが、Recタイプの定義は次のとおりです。誰がまだ定着液の「明白な」バージョンを指摘していない

-- | The 'Rec' type is an isomorphism between @Rec a@ and @Rec a -> a@: 
-- 
-- > In :: (Rec a -> a) -> Rec a 
-- > out :: Rec a  -> (Rec a -> a) 
-- 
-- In simpler words: 
-- 
-- 1. Haskell's type system doesn't allow a function to be applied to itself. 
-- 
-- 2. @Rec a@ is the type of things that can be turned into a function that 
-- takes @Rec a@ arguments. 
-- 
-- 3. If you have @foo :: Rec a@, you can apply @foo@ to itself by doing 
-- @out foo foo :: a@. And if you have @bar :: Rec a -> a@, you can do 
-- @bar (In bar)@. 
-- 
newtype Rec a = In { out :: Rec a -> a } 

-- | This version of 'fix' is just the Y combinator, but using the 'Rec' 
-- type to get around Haskell's prohibition on self-application (see the 
-- expression @out x x@, which is @x@ applied to itself): 
fix :: (a -> a) -> a 
fix f = (\x -> f (out x x)) (In (\x -> f (out x x))) 

Answer 2

私はこれがうまくいくと思う：無名関数をサポートするプログラミング言語で

myCycle = \xs -> fix (xs ++) 

http://en.wikipedia.org/wiki/Fixed-point_combinator

を、固定小数点コンビネータはすなわちずに、匿名の再帰関数の定義および使用を許可しますそのような機能を識別子に結びつけなければならない。この設定では、固定小数点コンビネータの使用は匿名再帰と呼ばれることがあります。楽しみのために

Answer 3

これは別のものです：

let f = foldr (++) [] . repeat 

または

let f = foldr1 (++) . repeat 

Answer 4

。考え方は、名前付き再帰呼び出しをパラメータに変換することです。

let realMyCycle = fix (\myCycle xs -> xs ++ myCycle xs) 

この「再帰的な名前」導入トリックは、ハスケルではほとんど何かである（let in）。唯一の違いは、組み込みのコンストラクトを使用する方がより簡単であり、おそらく実装にとってより良いことです。