haskell - サイクルをラムダ関数としてどのように記述しますか?

Question

楽しみのために、これが私の独自のバージョンですcycle：

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

右側は、関数名myCycleとパラメーターの両方を参照しますxs。

言及myCycle せずmyCycleに、またはxs右側に実装することは可能ですか?

myCycle = magicLambdaFunction

Answer 1

myCycle言及せずに、myCycleまたはxs右側に実装することは可能ですか?

答えは「はい」と「いいえ」です (必ずしもこの順序ではありません)。

他の人は固定小数点コンビネータについて言及しています。固定小数点コンビネータがある場合は、fix :: (a -> a) -> aPubby の回答へのコメントで述べたように、 と書くことができますmyCycle = fix . (++)。

しかし、 の標準的な定義fixは次のとおりです。

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

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

の定義でfixは、その定義の右側で左側の変数に言及する必要があることに注意してください (r最初の定義でfix'は、2 番目の定義では)。つまり、これまで実際に行ったことは、問題を単にfix.

興味深いことに、Haskell は型付きラムダ計算に基づいており、技術的な理由から、ほとんどの型付きラムダ計算は、固定小数点コンビネータを「ネイティブに」表現できないように設計されています。これらの言語は、固定小数点の計算を可能にする基本計算の「上に」追加機能を追加した場合にのみ、チューリング完全になります。たとえば、次のいずれかが実行されます。

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

これは、多くの理由で有用なタイプのモジュール性です。1 つは、不動点のないラムダ計算がロジックの一貫した証明システムでもあること、もう 1 つはfix、多くのそのようなシステムの少ないプログラムが終了することを証明できることです。

---

編集：ここで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