3

単語をアナグラムでグループ化する Haskell 関数を作成しました。OCaml を学ぼうとしていますが、OCaml でパターン マッチングを使用する方法について少し混乱しています。誰かがこれをOCamlに翻訳するのを手伝ってくれませんか? ありがとうございました！

この関数は文字列のリストを受け取り、アナグラムでグループ化された文字列リストのリストに分割します。

import Data.List

groupByAnagrams :: [String] -> [[String]]
groupByAnagrams []     = []
groupByAnagrams (x:xs) = let (listOfAnagrams, listOfNonAnagrams) = (partitionByAnagrams (sort x) xs)
                         in 
                         (x:listOfAnagrams):(groupByAnagrams listOfNonAnagrams)

このヘルパー関数は、並べ替えられた文字列sortedStrと文字列のリストを取ります (文字列が並べ替えられているのは、反復ごとに並べ替えを呼び出す必要がないためです)。文字列リストは 2 つのリストに分割されます。1 つは と のアナグラムである文字列で構成され、もう 1 つsortedStrはそうでない文字列で構成されます。この関数は、これら 2 つのリストで構成されるタプルを返します。

partitionByAnagrams :: String -> [String] -> ([String], [String])
partitionByAnagrams sortedStr []     = ([], [])
partitionByAnagrams sortedStr (x:xs) 
         | (sortedStr == (sort x))   = let (listOfAnagrams, listOfNonAnagrams) = (partitionByAnagrams sortedStr xs)
                                       in
                                       (x:listOfAnagrams, listOfNonAnagrams)
         | otherwise                 = let (listOfAnagrams, listOfNonAnagrams) = (partitionByAnagrams sortedStr xs)
                                       in
                                       (listOfAnagrams, x:listOfNonAnagrams)

これは単なるテストケースです:

test1 = mapM_ print (groupByAnagrams ["opts", "alerting", "arrest", "bares", "drapes", "drawer", "emits", "least", "mate", "mates", "merit", "notes", "palest", "parses", "pores", "pots", "altering", "rarest", "baser", "parsed", "redraw", "items", "slate", "meat", "meats", "miter", "onset", "pastel", "passer", "poser", "spot", "integral", "raster", "bears", "rasped", "reward", "mites", "stale", "meta", "steam", "mitre", "steno", "petals", "spares", "prose", "stop", "relating", "raters", "braes", "spared", "warder", "smite", "steal", "tame", "tames", "remit", "stone", "plates", "sparse", "ropes", "tops", "triangle", "starer", "saber", "spread", "warred", "times", "tales", "team", "teams", "timer", "tones", "staple", "spears", "spore"])

**編集！！！これは私の関数の書き直されたバージョンです。非効率性を指摘してくれた jrouquie に感謝します。** 10/7 に再度編集 - わかりやすくするためにタプルでパターン マッチングを使用しました。これらすべての fst と snd は必要ありません。

groupByAnagrams2 :: [String] -> [[String]]
groupByAnagrams2 str = groupBySnd $ map (\s -> (s, (sort s))) str

groupBySnd :: [(String, String)] -> [[String]]
groupBySnd []           = []
groupBySnd ((s1,s2):xs) = let (listOfAnagrams, listOfNonAnagramPairs) = (partitionBySnd s2 xs)
                          in
                          (s1:listOfAnagrams):(groupBySnd listOfNonAnagramPairs)


partitionBySnd :: String -> [(String, String)] -> ([String], [(String, String)])
partitionBySnd sortedStr []                = ([], [])
partitionBySnd sortedStr ((s, sSorted):ss)
              | (sortedStr == sSorted)     = let (listOfAnagrams, listOfNonAnagramPairs) = (partitionBySnd sortedStr ss)
                                             in
                                             (s:listOfAnagrams, listOfNonAnagramPairs)
              | otherwise                  = let (listOfAnagrams, listOfNonAnagramPairs) = (partitionBySnd sortedStr ss)
                                             in
                                             (listOfAnagrams, (s, sSorted):listOfNonAnagramPairs)
4

2 に答える 2

6

あなたの Haskell コードは少し不器用だと言わざるを得ません。つまり、元の関数はもっと簡潔に記述できたはずです。例えば：

import Control.Arrow ((&&&))
import Data.Function (on)
import Data.List (groupBy, sortBy)

anagrams :: Ord a => [[a]] -> [[[a]]]
anagrams =
  map (map fst) .
  groupBy ((==) `on` snd) .
  sortBy (compare `on` snd) .
  map (id &&& sortBy compare)

あれは：

  • map (id &&& sortBy compare)リスト内の各文字列をその文字のソート済みリストとペアにします。
  • sortBy (on compare snd)2 番目のコンポーネントにあるペアのリスト、つまりソートされた文字のリストをソートします。
  • groupBy (on (==) snd)並べ替えられた文字の同一のリストを持つ並べ替えられたリスト内のすべての連続するアイテムをグループ化します。
  • 最後に、map (map fst)ソートされた文字のリストを削除し、元の文字列だけを残します。

例えば：

Prelude> :m + Control.Arrow Data.Function Data.List

Prelude Control.Arrow Data.Function Data.List> ["foo", "bar", "rab", "ofo"]
["foo","bar","rab","ofo"]

Prelude Control.Arrow Data.Function Data.List> map (id &&& sortBy compare) it
[("foo","foo"),("bar","abr"),("rab","abr"),("ofo","foo")]

Prelude Control.Arrow Data.Function Data.List> sortBy (compare `on` snd) it
[("bar","abr"),("rab","abr"),("foo","foo"),("ofo","foo")]

Prelude Control.Arrow Data.Function Data.List> groupBy ((==) `on` snd) it
[[("bar","abr"),("rab","abr")],[("foo","foo"),("ofo","foo")]]

Prelude Control.Arrow Data.Function Data.List> map (map fst) it
[["bar","rab"],["foo","ofo"]]

Caml に「変換」すると、次のような結果が得られます。

let chars xs =
  let n = String.length xs in
  let rec chars_aux i =
    if i = n then [] else String.get xs i :: chars_aux (i + 1)
  in
  List.sort compare (chars_aux 0)

let group eq xs =
  let rec group_aux = function
    | [] -> []
    | [x] -> [[x]]
    | x :: xs ->
        let ((y :: _) as ys) :: yss = group_aux xs in
        if eq x y then (x :: ys) :: yss else [x] :: ys :: yss
  in
  group_aux xs

let anagrams xs =
  let ys = List.map chars xs in
  let zs = List.sort (fun (_,y1) (_,y2) -> compare y1 y2) (List.combine xs ys) in
  let zs = group (fun (_,y1) (_,y2) -> y1 = y2) zs in
  List.map (List.map fst) zs

ここで、ヘルパー関数charsは文字列を並べ替えられた文字リストに取りgroupますが、Caml でリストに対してパターン マッチングを行う方法についての洞察を与えるはずです。

于 2012-08-13T14:14:45.810 に答える
4

最も一般的なパターン マッチングの形式は式であり、Haskellmatchの式と同じです。case

let rec groupByAnagrams lst =
  match lst with [] -> ...
               | x::xs -> ...

ただし、関数の最後の引数のみをパターン マッチングする必要がある場合 (この場合のように)、次のfunction構文を使用したショートカットがあります。

let rec groupByAnagrams = function
    [] -> ...
  | x::xs -> ...

警備員に関しては、正確に同等のものはありません。パターン マッチ内で使用できますがwhen、それは特定のパターンにのみ適用され、必要なすべてのケースでそのパターンを繰り返す必要があります。も使用できますif ... then ... else if ... then ... else ...が、それほどきれいではありません。

let rec partitionByAnagrams sortedStr = function
    [] -> ...
    x::xs when ...(some condition here)... -> ...
    x::xs -> ...
于 2012-08-09T04:59:34.073 に答える