需要帮助重写一个Haskell程序,该程序通过OCaml(或任何ML)中的字谜对单词进行分组？

Question

我写了一个Haskell函数,用anagrams对单词进行分组.我正在尝试学习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和一个字符串列表(字符串排序的原因是我不必每次迭代都对它进行排序).字符串列表分为两个列表; 一个由字符串组成的字符串,sortedStr另一个字符串由字符串组成.该函数返回由这两个列表组成的元组.

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再次编辑 - 为了清晰起见,在元组上使用模式匹配,不需要所有那些fsts和snds.

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)

Answer 1

我不得不说我发现你的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) 对你现在拥有的第二个组件的对列表进行排序,即排序的字符列表;
• 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中的列表上进行模式匹配有所了解.