10

多くの関数はポイント自由形式に縮小できますが、これはすべての関数に当てはまりますか?

たとえば、次の場合はどうすればよいかわかりません。

apply2 f x = f x x
4

3 に答える 3

11

論理コンビネータ（つまり、S、K、Iコンビネータ）は本質的にポイントフリー形式の関数であり、ラムダ計算はコンビネータ論理と同等であるため、これは答えがイエスであることを示唆していると思います。

あなたの関数のコンビネータapply2は（私が物事を正しく読んでいる場合）：

((S((S(KS))K))(K((S((SK)K))((SK)K))))

RaymondSmullyanのCombinatoryBirdsページから「Lark」としても知られています。

（編集:)上記の1は。と同等であることがわかり\f x -> f (x x)ます。以下の「@gereeter」のコメントによると、それは確かに「ラーク」として知られています\f x -> f x xが、質問で要求された関数は、前述の本の「ウォーブラー」（別名「W」コンビネータ）ですW f x = S(S(K(S(KS)K))S)(KK)SI f x = S(S(KB)S)(KK)SI f x = CSI f x = SfIx = f x x。

ここに1：

((S((S(KS))K))(K((S((SK)K))((SK)K)))) f x =
  S( S(KS) K) (K( S( SK K) ( SK K)))  f x =   -- SKK    == I
  S (S(KS) K) (K( S  I       I    ))  f x =   -- S(KS)K == B
  S B         (K( S  I       I    ))  f x =
  Bf (K(SII)f) x = Bf (SII) x = f (SII x) = f (x x)
于 2012-11-01T20:04:14.063 に答える
11

SKベース

既に述べたように、コンビネータの適切な固定セットを使用すると、任意のラムダ項をそれらのコンビネータと関数適用のみを使用する形式に変換できます-ラムダ抽象化はありません(したがって変数はありません)。最もよく知られているコンビネータのセットはSandKです。手順の説明については、組み合わせロジック/SK 基底の完全性を参照してください。コンビネータは次のように定義されます。

K x y    = x
S x y z  = (x z) (y z)

恒等コンビネータIが含まれることもありますが、 として冗長I = S K Kです。

単一コンビネータベース

興味深いことに、単一のコンビネーターでもそれを行うことができます。イオタ言語は

U f = (f S) K

そして、それを示すことができます

I = (UU)
K = (U(U(UU)))
S = (U(U(U(UU))))

したがって、任意のラムダ項を形状以外の情報なしでバイナリ ツリーに変換できます (すべての葉には and が含まれU、ノードは関数の適用を表します)。

より効率的な基底 S、K、I、B、C

ただし、少し効率的になり、適切なサイズの変換を取得したい場合は、 and と呼ばれる 2 つの冗長コンビネータを使用しIて導入すると便利です。BC

C f x y  = f y x
B f g x  = f (g x)

ここではandCの引数の順序を逆にして関数合成をしています。fB

この追加により、出力の長さが大幅に短縮されます。

Haskell のこれらのコンビネータ

実際、Haskell には、これらすべての標準コンビネータが何らかの形で既に含まれています。特に：

I = id
K = const
  = pure :: a -> (r -> a)
S = (<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
B = (.)
  = (<$>) :: (a -> b) -> (r -> a) -> (r -> b)
C = flip
  = \k x -> k <*> pure x

ここでpure、<*>とは、ここでリーダー モナドに特化したファンクター型クラス<$>の関数です。Applicative(->) r

したがって、あなたの場合、次のように書くことができます

apply2 = (<*>) `flip` id

なぜ読者モナドなのか?

抽象化の除去の過程で、形式の項λx -> M :: r -> a(rは の型でxあり、aは の型M) を のない形式に変換しようとしxます。これを再帰的Mに処理することによって行い、その後、型の各部分項b( を含む可能性がある) を型( を含まない)xの関数に変換し、これらの部分項を結合します。そしてそれこそが、reader モナドが設計された目的です: 型の関数を一緒に結合するためです。r -> bxr -> something

詳細については、 The Monad Reader, Issue 17 : The Reader Monad and Abstraction Eliminationを参照してください。

データ構造はどうですか？

データ構造を構築するために、単純にそれらのコンストラクターを使用します。ここでは問題ありません。

それらを分解するには、パターン マッチングを取り除く何らかの方法が必要です。これは、関数型プログラムをコンパイルするときにコンパイラが行う必要があることです。このような手順は、関数型プログラミング言語の実装の第 5 章: パターン マッチングの効率的なコンパイルで説明されています。データ型ごとに、データ型を分解 (フォールド) する方法を説明するケース関数が 1 つあるという考え方です。たとえば、リストの it foldr、Eitheritseitherの場合、4 タプルの場合は次のようになります。

caseTuple4 :: (a -> b -> c -> d -> r) -> (a,b,c,d) -> r
caseTuple4 f (a,b,c,d) = f a b c d

そのため、各データ型に対して、そのコンストラクター、分解ケース関数を追加し、パターンをこの関数にコンパイルします。

例として、表現しましょう

map :: (a -> b) -> [a] -> [b]
map f []        = []   
map f (x : xs)  = f x : map f xs

これは次のように表現できますfoldr。

map f = foldr (\x xs -> f x : xs) []

次に、前述のコンビネータを使用して変換します。

map = (foldr . ((.) (:))) `flip` []

実際に私たちが望んでいることを確認できます。

上位の型を有効にした場合に、データ構造を関数として直接エンコードする方法について説明しているSystem F データ構造も参照してください。

結論

はい、コンビネータの固定セットを構築してから、これらのコンビネータと関数適用のみを使用するポイントフリー スタイルに任意の関数を変換できます。

于 2012-11-02T17:08:40.300 に答える
5

そうではないように見えても、ポイントフリー スタイルで表現できる関数はたくさんありますが、そうでない関数を取得するには、標準がない非常に大きなタプルで動作する関数をすばやく定義できます。機能。

この種のことは、複雑さのためではなく、このサイズのタプルの関数があまりないため、ポイントフリーで表現できる可能性は低いと思います:

weird (a,b,c,d,e,f,g,h,i,j) = (a<*>b,c++d,e^f+a,g ()-h 4+e,j <*> take f i)

あなたの例:

apply2 :: (b -> b -> a) -> (b -> a)
apply2 = join

それjoinはリーダーモナドにあります((->) b)

join :: Monad m => m (m a) -> m a

だからこの場合

join :: ((->) b) ((->) b a) -> ((->) b) a
join :: ((->) b) (b -> a) -> (b -> a)
join :: (b -> (b -> a)) -> (b -> a)
join :: (b -> b -> a) -> (b -> a)

予想以上に多くの関数にポイントフリー バージョンがありますが、一部のポイントフリー式は完全に混乱しています。場合によっては、簡潔にするよりも明示的にする方がよい場合があります。

于 2012-11-01T19:45:20.980 に答える