3

私は Haskell を使い始めたばかりで、この単純な再帰アルゴリズムを打ち出して、リスト内のすべての数値の LCM を見つけました。これは機能しますが、面倒なので、これをよりエレガントで読みやすく、Haskell-y にする方法についてのピアレビューを期待していました。

lcms list 
  | length list > 1 = lcms (lcm (head list) (head (tail list)):(tail (tail list)))
  | otherwise = list

つまり、リストを取得して最初の 2 つの項目の LCM を実行し、それを先頭に追加して、それらの 2 つの要素を除いたリストに追加します。基本的に、私が目指している疑似コードは次のようなものです。

lcms [a,b,c] = lcm (a, (lcm (b, c))

何か提案はありますか？私は Haskell を改善し、人々が実際に読めるものを書きたいと思っています。効率化のヒントも大歓迎です！

皆さんありがとう！

4

2 に答える 2

3

あなたが提案したほとんどの構文でそれを書くことができます。

lcms (a:b:c) = lcms (lcm a b:c)
lcms list = list

2 番目の句は少し奇妙ですが、ひどいものではありません。空のリストを適切に処理しますが、多くても 1 つの項目を返すことがわかっている場合にリストを返すことは、一部のハゾヒストによって、型が少し不正確であると見なされる可能性があります。Maybe正規の 0 または 1 要素タイプである の使用を検討することもできます。

lcms (a:b:c)  = lcms (lcm a b:c)
lcms [answer] = Just answer
lcms []       = Nothing

別の良い選択は、健全な基本ケースを特定することです。二項演算の場合、演算の単位は通常適切な選択であるため、 のlcm場合は を選択します1。

lcms (a:b:c)  = lcms (lcm a b:c)
lcms [answer] = answer
lcms []       = 1

一般に、可能な場合は明示的な再帰を避けようとします。他の答えは、そのステップを実行する方法を示しています。この場合、基本ケースをより美しくする中間の変換があります。リストの先頭にアキュムレータを保持する代わりに、アキュムレータがリスト要素と同じ型であるため、偶然にのみ機能します。累積をより明示的にまたはより少なくすることができます。したがって、次のいずれかです。

lcms (x:xs) = lcm x (lcm xs)
lcms []     = 1

-- OR

lcms = go 1 where
    go acc (x:xs) = go (lcm acc x) xs
    go acc []     = acc

これら 2 つの実装は、明示的な再帰を選択foldrまたは削除することに対応しています。2番目のものに似ていますが、余分なものがあります:foldlfoldl'seq

lcms = go 1 where
    go acc (x:xs) = let acc' = lcm acc x in acc' `seq` go acc' xs
    go acc []     = acc
于 2015-08-23T03:03:05.683 に答える