13

Haskellの高階関数に慣れてきました。通常、再帰の明示的なパターンを、マップ、フォールド、スキャンなどの関数に置き換えることができます。ただし、高階関数を使用して表現する方法がわからない次の再帰パターンに遭遇することがよくあります。

   f (x:[]) = k x
   f (x:xs) = g x (f xs)

たとえば、私が分析タブローを代表しているとしましょう。次に、次のようなデータ型を作成します。

   data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau)

sのリストをExprタブロー構造に変換する場合は、次のような関数部分が必要です。

   f (x:[]) = N x
   f (x:xs) = S x (f xs)

ここで、3つのオプションが表示されます。（1）タブローとリストを指定して、タブローの次のブランチをSor N（または、、Bただしその場合は無視します）にするかどうかを決定する関数を作成します。（2）高階関数を使用してf;の再帰パターンをカプセル化します。（3）のような関数を使用しますf。

最良の選択肢は何でしょうか？

4

2 に答える 2

8

私はおそらく次のものを使用します：

f xs = foldr g (k (last xs)) (init xs)

k x基本的には、リストの最後が折りたたみ時に置き換えられることを意味します。どこにでもある遅延評価のおかげで、無限リストでも機能します。

他に 2 つの解決策があります - 空のケースを追加することと、Maybe を使用することです。

A) 空のケースを追加:

f []が明確に定義されている場合に最適です。次に、定義を次のように書くことができます

f [] = c
f (x:xs) = g x (f xs)

ですf = foldr g c。たとえば、

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau

に

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau

次に、単一要素の tableaux を として表すことができS expr N、関数はワンライナーとして定義されます

f = foldr S N

空のケースが理にかなっている限り、これが最善の解決策です。

B) メイビーを使用:

一方、f []賢明に定義できない場合は、さらに悪いことになります。部分的な関数はしばしば醜いものと見なされます。合計するには、 を使用できますMaybe。定義

 f [] = Nothing
 f [x] = Just (k x)
 f (x:xs) = Just (g x w)
            where Just w = f xs

これは総合的な機能です。その方が優れています。

しかし、関数を次のように書き換えることができます。

 f [] = Nothing
 f (x:xs) = case f xs of
              Nothing -> Just (k x)
              Just w -> Just (g x w)

これは正しい折り方です:

 addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux
 addElement x Nothing = Just (N x)
 addElement x (Just w) = Just (S x w)

 f = foldr addElement Nothing

一般に、折りたたみは慣用的であり、再帰パターンに適合する場合に使用する必要があります。それ以外の場合は、明示的な再帰を使用するか、既存のコンビネータを再利用してください。新しいパターンがある場合は、コンビネータを作成しますが、そのパターンを頻繁に使用する場合に限ります。そうでない場合はやり過ぎです。この場合、次のように定義された空でないリストのパターンは fold ですdata List a = End a | Cons a (List a)。

于 2010-08-01T02:41:55.420 に答える
4

質問を適切に理解した場合、あなたの選択肢に対する私の評価は次のとおりです。

  1. その関数を書くために、コンストラクターの下から (おそらく恣意的に複雑な?) テーブルを一致させなければならないのは、おそらく少し厄介です。このアプローチは、おそらく問題なく機能しますが、やや脆弱に見えます。

  2. 再帰構造で動作する再帰関数であることを考えると、パターンを一般化する必要はないと思います。高次のパターンを導入すると、このデータ構造の再帰的なトラバーサルを実行する背後にある実際のロジックが難読化されると思います。

  3. これはかなり理にかなっていると思います。お察しのとおり、それなりに認められた「パターン」ですが、このように書くのがアルゴリズムの記述とよく合っていると思います。一般化可能または再利用可能ではないかもしれませんが、本質的にアルゴリズム アプローチの核心であることを考えると、f のような関数で行ったようにケースを直接記述することは理にかなっていると思います。これは私の好みのアプローチです。

特に具体的な回答を提供できなくて申し訳ありませんが、これはかなり主観的な回答であるため、上記の 3 つのオプションを考慮して、明確さと読みやすさの理由からオプション 3 を選択します。

于 2010-08-01T01:25:35.170 に答える