20

私は、パターンマッチングに関して、Haskellリスト内包表記が「内部」でどのように機能するかを理解しようとしています。次のghci出力は、私のポイントを示しています。

Prelude> let myList = [Just 1, Just 2, Nothing, Just 3]
Prelude> let xs = [x | Just x <- myList]
Prelude> xs
[1,2,3]
Prelude>

ご覧のとおり、「Nothing」をスキップして「Just」の値のみを選択することができます。リストはモナドであり、次のように定義されていることを理解しています(Real World Haskell、ch。14からの出典):

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    xs >> f = concat (map (\_ -> f) xs)
    fail _ = []

したがって、リスト内包は基本的に、リスト内包で選択されたすべての要素に対してシングルトンリストを作成し、それらを連結します。あるステップでパターン一致が失敗した場合、代わりに「失敗」関数の結果が使用されます。つまり、「Just x」パターンが一致しないため、「concat」が呼び出されるまで[]がプレースホルダーとして使用されます。これが、「何も」がスキップされているように見える理由を説明しています。

私が理解していないのは、Haskellが「失敗」関数を呼び出すことをどのように知っているのかということです。それは「コンパイラの魔法」なのか、それともHaskellで自分で書くことができる機能なのか?次の「選択」関数を記述して、リスト内包表記と同じように機能させることはできますか?

select :: (a -> b) -> [a] -> [b]
select (Just x -> x) myList       -- how to prevent the lambda from raising an error?
[1,2,3]
4

3 に答える 3

33

Haskell の実装では、内部的にこのように直接行うことはできないかもしれませんが、このように考えると役に立ちます :)

[x | Just x <- myList]

... になります:

do
    Just x <- myList
    return x

...つまり:

myList >>= \(Just x) -> return x

あなたの質問について:

私が理解していないのは、Haskell が「失敗」関数を呼び出すことをどのように知っているかということです。

do 記法では、パターン バインディングが失敗した場合 (つまりJust x)、fail メソッドが呼び出されます。上記の例では、次のようになります。

myList >>= \temp -> case temp of
    (Just x) -> return x
    _        -> fail "..."

したがって、失敗する可能性のあるモナド コンテキストでパターン マッチが発生するたびに、Haskell は への呼び出しを挿入しますfail。IO で試してみてください:

main = do
    (1,x) <- return (0,2)
    print x -- x would be 2, but the pattern match fails
于 2009-03-17T06:27:24.470 に答える
10

リスト内包表記を脱糖化するための規則には、次のような形式の式が必要です[ e | p <- l ](ここeで、 は式、pパターン、およびlリスト式です)。

let ok p = [e]
    ok _ = []
in concatMap ok l

以前のバージョンの Haskell にはモナド内包表記がありましたが、これは読みにくく、- 表記で冗長だったため、言語から削除されましたdo。(リスト内包表記も冗長ですが、それほど難しくはありません。)モナドとして(または、正確にはゼロのモナドとして) desugar すると、次のような結果が得られると思います。[ e | p <- l ]

let ok p = return e
    ok _ = mzero
in l >>= ok

クラスのどこmzeroからですか。MonadPlusこれは非常に近いです

do { p <- l; return e }

するもの

let ok p = return e
    ok _ = fail "..."
in l >>= ok

リストモナドを取ると、

return e = [e]
mzero = fail _ = []
(>>=) = flip concatMap

つまり、3 つのアプローチ (リスト内包表記、モナド内包表記、do式) はリストに対して同等です。

于 2009-03-16T14:30:46.720 に答える
6

[]リスト内包表記の構文は、List ( )MaybeがたまたまMonad型クラスのインスタンスであるという事実とあまり関係がないと思います。

リスト内包表記は確かにコンパイラの魔法または構文の砂糖[]ですが、コンパイラはデータ型の構造を知っているため、それが可能です。

リスト内包表記は次のようにコンパイルされます: (まあ、GHC に対して実際にチェックしていないと思います)

xs = let f = \xs -> case xs of
                      Just x -> [x]
                      _      -> []
     in concatMap f myList

ご覧のとおり、コンパイラは関数を呼び出す必要はありません。リストfail何であるかを知っているため、単に空のリストをインライン化できます。


興味深いことに、リスト内包表記の構文がパターン一致の失敗を「スキップ」するというこの事実は、一部のライブラリで汎用プログラミングを行うために使用されています。Uniplate ライブラリの例を参照してください。


編集:ああ、あなたの質問に答えるために、select指定したラムダで関数を呼び出すことはできません。値を指定して呼び出すと、パターン一致の失敗で実際に失敗しNothingます。

f上記のコードの関数を渡すこともできますselectが、次のタイプになります。

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

これはまったく問題ありません。concatMap関数を内部的に使用できます:-)

また、その newselectはリストのモナド バインド演算子の型を持ちます (引数が反転されます)。

(>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = concatMap f xs -- 'or as you said: concat (map f xs)
于 2009-03-16T08:35:27.557 に答える