この関数はポイントフリースタイルで記述できますか?そうでない場合、なぜですか?

14
Enlico 2020-07-09 10:22.

関連する質問の1つはこれですが、回答の中には、ほとんどすべてのものをポイントフリーにすることができると言われているので、この関数の何が問題になっていますか?

\[x] -> x

http://pointfree.io/ポイントフリースタイルで書くことができないようです。これは、そのように書くことができないという意味ですか?もしそうなら、それの理論的な理由は何ですか?

上記の関数は、シングルトンリストでのみ動作できる「不自由な」バージョンhead(またはlastfwiw)であることがわかります。実際、シングルトン以外のリストに適用すると、次のようにエラーが発生しますghci

*** Exception: <interactive>:380:5-13: Non-exhaustive patterns in lambda

たぶん、パターンの「非網羅性」が、一部の関数をポイントフリースタイルで記述できない理由ですか?

答えに照らして編集します。

私の質問に対する答えがそれほど複雑になるとは思っていなかったので(短い答えはノーだと思っただけで、実際にはできません)、それらを注意深く読み、少し実験して、それらの周りに私の心を包みます、さもなければ私はどちらが受け入れられるべきかを決めることができません。とりあえず、Jon Purdyの答えに+1します。これまでは簡単に理解できました。これは、通常のコードで停止する場所です

3 answers

9
Silvio Mayolo 2020-07-09 10:41.

確かに、ほとんど何でもポイントフリーにすることができます。トリッキーなことは、結果の式で許可する関数です。パターンマッチングの場合、通常、代わりにマッチングを行うためにfold関数が必要です。したがって、たとえば、でパターンを一致させた場合はMaybe a、それをmaybe。に置き換える必要があります。同様に、Either a bパターンは。で書くことができますeither

署名のパターンに注意してください

data Maybe a = Nothing | Just a

maybe :: b -> (a -> b) -> (Maybe a -> b)

Maybe a2つのコンストラクターがあります。1つは引数をとらず、もう1つはa。を取ります。したがってmaybe、2つの引数を取ります。1つは0項関数(b)であり、もう1つはaa -> b)を取り、から関数を返しますMaybe a -> b。同じパターンがに存在しますeither

data Either a b = Left a | Right b

either :: (a -> c) -> (b -> c) -> (Either a b -> c)

2つのケース。最初のものはを取り、私たちが望むaものcを生成します。2番目はabを取り、c必要なものを生成します。いずれの場合も、sumタイプの可能な項ごとに1つの関数が必要です。

のような関数を体系的にポイントフリーにするに\[x] -> xは、同様のフォールドが必要です。[a]として宣言され、本質的に

data [a] = [] | a : [a]

したがって、このシグネチャを持つ関数が必要になります

list :: b -> (a -> [a] -> b) -> ([a] -> b)

今、flip foldr近づく

flip foldr :: b -> (a -> b -> b) -> ([a] -> b)

しかし、それは再帰的です。これは、上の提供関数を呼び出す[a]の一部a : [a]。Haskellの基本ライブラリでは提供されていない真のフォールドが必要です。Hoogleをすばやく検索すると、この関数はと呼ばれるパッケージに存在することがわかりますextra。もちろん、この小さな例では、自分で簡単に書くことができます。

list :: b -> (a -> [a] -> b) -> ([a] -> b)
list f g x = case x of
               [] -> f
               (y:ys) -> g y ys

今、私たちはあなた\[x] -> xにそれを簡単に適用することができます。最初に、すべての厄介なundefinedケースを含めて、関数が実際に何をするかを書いてみましょう(undefined簡潔にするために、ここでは長いエラーメッセージではなく使用します)

func :: [a] -> a
func x = case x of
           [] -> undefined
           (y:ys) -> case ys of
                       [] -> y
                       (_:_) -> undefined

これで、すべてのcaseステートメントが各コンストラクターと正確に1回一致します。これは、折り目に変換するのに熟しています。

func :: [a] -> a
func x = case x of
         [] -> undefined
         (y:ys) -> list y undefined ys

そして今、私たちはアウターケースも変形させます

func :: [a] -> a
func x = list undefined (\y -> list y undefined) x

だから私たちは持っています

func :: [a] -> a
func = list undefined (\y -> list y undefined)

または、本当に夢中になりたい場合

func :: [a] -> a
func = list undefined (flip list undefined)

しかし、この関数はベースにありません

ええ、それは本当です。存在しなかった折り目を使って、ちょっとごまかしました。体系的に実行したい場合は、その折り畳み演算子が必要です。しかし、それがなくても、私たちはそれを一緒に揉むことができfoldr1ます。これは私たちの特定の目的には十分です。

func' :: [a] -> a
func' = foldr1 (const (const undefined))

したがって、あなたの質問に答えるために、正しい署名を持つフォールド関数がない限り、例のようなパターンマッチングを常に体系的にポイントフリーに置き換えることはできません。幸い、その関数は、Haskell 98のデータ型(おそらくGADTも同様ですが、その可能性については深く考えていません)に対して、いつでも記述できます。しかし、そのサポートがなくても、私たちはそれを機能させることができます。

19
HTNW 2020-07-09 10:41.

ええと、データ型は関数ではありません。関数がデータ値をアンラップしていない限り(つまり、関数/コンストラクター間でデータ値をシャッフルしているだけ)、ポイントフリーで記述できますが、ポイントフリーマッチングの構文はありません。ただし、必要なのは、データ型ごとに1つの非ポイントフリー関数(fold)だけです。Haskellでは、データ型はほとんどフォールドによって定義されます。関連するデータ型のフォールドをプリミティブとして使用すると、任意のファンクションポイントを自由に書き換えることができます。実際には、いくつかの可能な「折り目」があることに注意してください。の場合[a]、再帰的なもの(Church /Böhm-Berarducciエンコーディングから取得)はfoldr :: (a -> b -> b) -> b -> [a] -> bです。もう1つの可能なフォールドは、Scottエンコーディングに由来する「-but case-it's-a-function」です(a -> [a] -> b) -> b -> [a] -> b(再帰は、fix別の「ポイントフリープリミティブ」である、で回復できます)が、@ SilvioMayoloが指摘しているように標準ライブラリではそのような関数ではありません。どちらでもかまいませんが、後者は事前定義されていないため、を使用してみましょうfoldr

\[x] -> x

書くことができます

fst . foldr (\x f -> (snd f x, \_ -> error "got (_ : _ : _) wanted [x]")) (error "got [] wanted [x]", id)
-- I don't care enough to replicate the exact exceptions.
-- this is "flattened" from
let fold [] = (error "got [] wanted [x]", id)
    fold (x : xs) = (snd (fold xs) x, \_ -> error "got (_ : _ : _) wanted [x]")
in  fst . fold

fold基本的にペアを返します(what to return if this was the entire list, how to transform the head if it wasn't)。の場合[]、それがリスト全体である場合はエラーを返しますが、それ以外の場合は、を押す直前に要素を通過し[]ます。の場合x : xs、その前に要素がある場合は無視してエラーを返し、ない場合はに渡します。これにより、エラーが発生snd (fold xs)するかどうxs = []かがチェックされます。すべての一致を排除したので、これをpointfree.ioに突き刺して、\x f -> _inをfoldroutへの引数にします。

behead = fst . foldr (flip flip (const (error "got (_ : _ : _) wanted [x]")) . ((,) .) . flip snd) (error "got [] wanted [x]", id)
ghci> :t behead
behead :: Foldable t => t c -> c
ghci> behead []
*** Exception: got [] wanted [x]
ghci> behead [1]
1
ghci> behead [1, 2]
*** Exception: got (_ : _ : _) wanted [x]
ghci> behead [1..]
*** Exception: got (_ : _ : _) wanted [x]

美しい。

注:この回答の以前のバージョンでは、「インライン化された」補助データ型が使用されていました。これは、基本的に、私が書いているときに「私に来た」ためです。ただし、無限リストを適切に処理できませんでした(behead [1..]ハングします)。このバージョンでは、組み込みのペアを補助データ型として使用します。これは、ポイントフリーにするためにインライン化する必要がないほど十分なライブラリサポートを備えています。インライン化するのは少し難しいので(,)fstとの実装内のポイントフルネスを排除しますが、この新しいタイプを使用するとsnd、それでも可能です。

newtype Pair a b = Pair { unPair :: forall r. (a -> b -> r) -> r }

または、タイプを少しごまかして、これを使用します。

-- residual pointfullness can be reduced by pointfree.io
\xs -> foldr (\x r f -> f (r (const id) x) (\_ -> error "got (_ : _ : _) wanted [x]")) (\f -> f (error "got [] wanted [x]") id) xs (\x _ _ -> x) undefined
6
Jon Purdy 2020-07-09 12:39.

これをポイントフリー形式で記述する簡単な方法は、フォールドを使用することです。ここで、アキュムレータの状態は次のいずれかです。

  • :要素はまだ表示されていません。それを保つ

  • フル:要素を見てきました。エラーを発生させる

最終状態がEmptyの場合、エラーも発生します。このアキュムレータは、次のように自然に表すことができますMaybe

fromSingleton :: (Foldable t) => t a -> a
fromSingleton
  = fromMaybe (error "empty list")
  . foldr (flip maybe (error "plural list") . Just) Nothing

これは私が通常のコードで停止するところです。だが…

補助データ型を使用したくない場合は、MaybeBöhm–Berarducciエンコーディングで表すことでを取り除くことができます。

type Maybe' r a
  = r          -- ‘Nothing’ continuation
  -> (a -> r)  -- ‘Just’ continuation
  -> r         -- Result

just' :: a -> Maybe' r a
-- just' = \ x _n j -> j x
just'
  = const     -- Ignore ‘Nothing’ continuation
  . flip ($) -- Apply ‘Just’ continuation to value nothing' :: Maybe' r a -- nothing' = \ n _j -> n nothing' = const -- Ignore ‘Just’ continuation maybe' :: r -> (a -> r) -> Maybe' r a -> r -- maybe' = \ n j k -> k n j maybe' = flip -- Apply to ‘Just’ continuation . flip ($)  -- Apply to ‘Nothing’ continuation

fromMaybe' :: r -> Maybe' r r -> r
-- fromMaybe' = \ n k -> k n id
fromMaybe' = flip maybe' id  -- Pass ‘id’ as ‘Just’ continuation

しかし、私たちはただの卸売交換を行うことができないJustとしjust'maybemaybe'ように、と。タイプはうまくいきません:

> :t fromMaybe' (error "empty list") . foldr (flip maybe' (error "plural list") . just') nothing'

<interactive>:…:…: error:
    • Occurs check: cannot construct the infinite type: c ~ Maybe' c c
      Expected type: c -> Maybe' c c -> Maybe' c c
        Actual type: c -> Maybe' (Maybe' c c) c -> Maybe' c c
    • In the first argument of ‘foldr’, namely
        ‘(flip maybe' (error "plural list") . just')’
      In the second argument of ‘(.)’, namely
        ‘foldr (flip maybe' (error "plural list") . just') nothing'’
      In the expression:
        fromMaybe' (error "empty list")
          . foldr (flip maybe' (error "plural list") . just') nothing'

問題はMaybe'Maybe'継続からを返し、コンパイラが2つの結果タイプを統合しようとしていることです。1つの解決策は、最初にeta-expandを実行して、タイプチェッカーに個別の関数を作成する場所を通知することです。

> :t fromMaybe' (error "empty list") . foldr (\ x acc -> \ n j -> maybe' (just' x n j) (error "plural list") acc) nothing'

fromMaybe' (error "empty list") . foldr (\ x acc -> \ n j -> maybe' (just' x n j) (error "plural list") acc) nothing'
  :: Foldable t => t c -> c

次に、ポイントフリー形式に段階的に書き換えることができます。

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n j
        -> maybe'
          (just' x n j)
          (error "plural list")
          acc)
    nothing'

-- Move ‘n’ & ‘j’ past ‘error …’ with ‘flip’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n j
        -> flip maybe'
           ----
          (error "plural list")
          (just' x n j)
          acc)
    nothing'

-- Move ‘n’ & ‘j’ past ‘acc’ with ‘flip’ again:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n j
        -> flip (flip maybe' (error "plural list")) acc
           ----
          (just' x n j))
    nothing'

-- Eta-reduce ‘j’ with composition:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n
        -> flip (flip maybe' (error "plural list")) acc
          . just' x n)
          --
    nothing'

-- Eta-reduce ‘n’ with ‘fmap’ (to map “under” an argument):

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> fmap (flip (flip maybe' (error "plural list")) acc)
         ----
        . just' x)
    nothing'

-- Move ‘x’ rightward with ‘flip’ on the outside:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc x
     ----
      -> fmap (flip (flip maybe' (error "plural list")) acc)
        . just' x))
    nothing'

-- Replace composition with ‘fmap’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc x
      -> fmap (fmap (flip (flip maybe' (error "plural list")) acc))
         ----
        (just' x)))
    nothing'

-- Eta-reduce ‘x’ with composition:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc
      -> fmap (fmap (flip (flip maybe' (error "plural list")) acc))
        . just'))
        --
    nothing'

-- Replace composition with ‘fmap’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc
      -> fmap (fmap (fmap (flip (flip maybe' (error "plural list")) acc)))
         ----
        just'))
    nothing'

-- Move ‘acc’ rightward with ‘flip’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc
      -> flip fmap just'
         ----
        (fmap (fmap (flip (flip maybe' (error "plural list")) acc)))))
    nothing'

-- Eta-reduce with composition:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip
      (flip fmap just'
        . fmap . fmap . flip (flip maybe' (error "plural list"))))
        --     -      -
    nothing'

これも完全にポイントフリーです(元のコードよりもはるかに読みにくいですが、pointfree生成されるものよりは優れています)。実際、ポイントフリーコードでは、fromMaybe'すべてをインライン化する代わりに、のような多くの小さな補助定義を使用することをお勧めしますが、それらの定義をインライン化することもできます。

ただし、それらを単純にインライン化してまったく同じタイプを取得することはできません。そうすると、に到達し(Foldable t) => t (a -> b) -> a -> bます。期待されるタイプを取得するために、eta-expandとrewriteが必要な場所で作業することは良い練習になるかもしれません(Foldable t) => t a -> a

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

Intelはついに適切なグラフィックカードに取り組んでいます

Intelはついに適切なグラフィックカードに取り組んでいます

画像:Intel AMDは、新しいRyzenチップのおかげで、今年はIntelで懸命に取り組んできましたが、AMDのリードGPUアーキテクトであるRaja KoduriがIntelの新しい上級副社長になり、その責任者になることで、Intelは最後の笑いを得るかもしれません。新たに結成されたコアおよびビジュアルコンピューティンググループ。PCの最大のCPUメーカーは、ついにGPUに適切に投資しています。

Fossilの新しいスマートウォッチは、ペブルファンが待ち望んでいたものです

Fossilの新しいスマートウォッチは、ペブルファンが待ち望んでいたものです

それは格好良い時計の人々です。Pebbleファンは必然的に、受信トレイ、コメント、DMで忠実でありながら死にかけているスマートウォッチを称賛することは、スマートウォッチのレビュー担当者に広く知られている真実です。

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

Tomorrow's Kitchen シリコンストレッチ蓋 12個パック | $14 | アマゾン | プロモーション コード 20OFFKINJALids は基本的にキッチンの靴下です。常に迷子になり、二度と閉じられない孤立したコンテナーが残ります。しかし、蓋が伸びて、残った容器、鍋、フライパン、さらには大きなスライスされた果物のすべてに適合するとしたらどうでしょうか? その非常に特殊な蓋を失うことを二度と心配する必要はありません。

あなたの最高のワシントン DC ハックを教えてください

あなたの最高のワシントン DC ハックを教えてください

このコラムでは、ロサンゼルスやラスベガスなど、いくつかの産業都市をハッキングしました。今こそ、軍産複合都市の時代です。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

Language