ハスケルの組合せ

ジオンムンジンジン
許可Open Software License 3.0

私の好きな言語の間に戦争があった。

そして、私はHaskellで組合せを作る方法に夢中です.

Haskellシリーズの組合せ

Combinations In Haskell (called Tail After Tail)

テールストーリー後のテール

同じ説異なる実装

プログラミング世界では、擬似コードや理論は、多くの方法でプログラミングの実装をトリガします.この種の転換は、同様にプログラミングをおもしろくします.
以前私はTailAfterTail.lhs
私は inits or tails 私が頼らないならば、全く必要でありませんscanl or zipWith .
ごく少量のコードで構成されているが、非常に高い周波数で動作するいくつかの異なった実装が、実行の多くの反復の後にパフォーマンスの大きなギャップを最終的に示すでしょう.
したがって、これは尾の組み合わせの後に尾の実装中に見つけたものです.

モジュール開始

まず、すべての機能を書き留めるつもりです.

{-# LANGUAGE BangPatterns #-}

module TailAfterTail
  ( combinationsWithScanl
  , combinationsWithSingleStep
  , combinations
  , combinationsWithTwoSteps
  , allCombinationsWithScanl
  , allCombinationsWithSingleStep
  , allCombinationsWithTwoSteps
  , allCombinations
  ) where

import Data.List (tails, inits, scanl') -- only required for **WithScanl

オリジナルバージョン

詳細情報をご覧くださいHERE .
しかしcombinations1' , flatten_allCombinationsGrouped andgenPart 共通のヘルパー関数になります.

combinations1' :: [a] -> [[[a]]]
combinations1' ms = [ [[m]] | m <- ms ]

flatten_allCombinationsGrouped allComboFunc = map concat . allComboFunc

genPart :: Foldable t => a -> t [[a]] -> [[a]]
genPart leader followerGroups = [ leader : followers
                                  | followers <- concat followerGroups ]

そしていくつかのヘルパー関数を定義します.

usefulTails :: [a] -> [[a]]
usefulTails = init . tails

genStep :: [[[a]]] -> [a] -> [[[a]]]
genStep prevTails members' =
  zipWith genPart members' (usefulTails prevTails')
  where
    prevTails' = tail prevTails -- head is not useful

membersTails = reverse . tail . inits -- tail is used to skip empty list.

そしてついにcombinationsWithScanl 家族は下に行きます.

allCombinationsWithScanl' :: [a] -> [[[[a]]]]
allCombinationsWithScanl' ms =
  scanl' genStep (combinations1' ms) (membersTails ms)

allCombinationsWithScanlGrouped :: [a] -> [[[a]]]
allCombinationsWithScanlGrouped =
  flatten_allCombinationsGrouped allCombinationsWithScanl'

allCombinationsWithScanl :: [a] -> [[a]]
allCombinationsWithScanl = concat . allCombinationsWithScanlGrouped

SANLを使用しない純粋な実装( singlestep )

scanlまたはzipbyなしで次のコードが作成されます.
それはわずかにより多くのパフォーマンスを得ます.
これは別の記事にあるかもしれません.
しかし、IMHOは、それは怠惰を減らすために、より少ないスタックを使用するのに役立ちます.

unsafe_allCombinationsWithSingleStep :: [a] -> [[[[a]]]]
unsafe_allCombinationsWithSingleStep members =
  let
    helper ! cases = -- bang pattern added
      let
        genStep (m:ms) (_:cs:[]) = [ [ m : c | c <- cs ] ]
        genStep (m:ms) (_:cs) =
          -- note       ^ : we don't use first element
          genPart m cs : genStep ms cs
      in
         cases : helper (genStep members cases)
  in
    helper . combinations1' $ members

ご覧の通りhelper 関数はエントリレベルのラッパー関数であり、再帰呼び出しを行う.genStep 実際に次のケースを作成し、Haskellのlazinessのおかげで後で評価されるthunkとして動作します.
私はその関数をunsafe_ 故意に.ヘルパー機能は実際には停止するときに知っているので、実行している場合unsafe_allCombinationsWithSingleStep 裸の文脈では、例外で爆発します.

sh> ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /your/home/.config/ghc/ghci.conf
λ> :l 2022-04-15-Combinations-TailAfterTail'.lhs
[1 of 1] Compiling TailAfterTail    ( 2022-04-15-Combinations-TailAfterTail'.lhs, interpreted )
Ok, one module loaded.
λ> unsafe_allCombinationsWithSingleStep [1..5]
[[[[1]],[[2]],[[3]],[[4]],[[5]]],[[[1,2],[1,3],[1,4],[1,5]],[[2,3],[2,4],[2,5]],[[3,4],[3,5]],[[4,5]]],[[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5]],[[2,3,4],[2,3,5],[2,4,5]],[[3,4,5]]],[[[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5]],[[2,3,4,5]]],[[[1,2,3,4,5]]],[[]*** Exception: 2022-04-15-Combinations-TailAfterTail'.lhs:(120,9)-(122,52): Non-exhaustive patterns in function genStep

unsafe_allCombinationsWithSingleStepGrouped 結果を平らにするが、選択サイズでグループ化したが、これはまだ安全ではない combinationsWith は処理します.

unsafe_allCombinationsWithSingleStepGrouped :: [a] -> [[[a]]]
unsafe_allCombinationsWithSingleStepGrouped =
  flatten_allCombinationsGrouped unsafe_allCombinationsWithSingleStep

それで、我々はより多くの時間を平らにすることによって、すべての組合せを得ることができました.

allCombinationsWithSingleStep :: [a] -> [[a]]
allCombinationsWithSingleStep members =
  concat
  --  this makes unsafe_* safe by limiting the size of list.
  . take (length members)
  . unsafe_allCombinationsWithSingleStepGrouped
  $ members

2歩で

これは別のバージョンなしscanl . 主な改善は
この関数はジョブを2つの操作に分離します:

前の尾から最初のケースを作成します.

ケースの残りを作成し、結果に基づいて次の次のケースを開始します.

allCombinationsWithTwoSteps' :: [a] -> [[[[a]]]]
allCombinationsWithTwoSteps'
  members@(fm:rms) = -- ^ fm : first member; rms: rest members
  let
    initFirstCase = [[fm]]
    initRestCases = combinations1' rms

    genFirstCases = genPart fm

    genRestCases _ [] = []
    genRestCases (m:ms) rcs@(_:rcs') = -- ^ rcs : rest of cases
      (genPart m $ rcs) : (genRestCases ms rcs')

比較するとほぼ同じに見えるSingleStep でも
現在helper 関数は、どこから始まるべきかを正確に知るnewTail is
今すぐ覚えなさい.時間を節約するtail パターンマッチング
インSingleStep しかし、選択肢が成長しているとき、Ressutsは伝播されます.
ところで、tail 以下のコードで、パターンマッチング手段(Con : CS)によって.

        genStep (m:ms) (_:cs) =
          -- note       ^ : we don't use first element
          [ m : c | c <- concat cs ] : genStep ms cs

そして、最初のケースとヘルパー機能でそれらを配線しましょう

    helper [] = []
    helper ! prevTail =
      let
        newTail = genRestCases rms (tail prevTail)
      in
        ((genFirstCases prevTail) : newTail) : helper newTail
  in (initFirstCase : initRestCases) : helper initRestCases

以下の手順は他の実装と同様です.

allCombinationsWithTwoStepsGrouped :: [a] -> [[[a]]]
allCombinationsWithTwoStepsGrouped =
  flatten_allCombinationsGrouped allCombinationsWithTwoSteps'

allCombinationsWithTwoSteps :: [a] -> [[a]]
allCombinationsWithTwoSteps members =
  concat . allCombinationsWithTwoStepsGrouped $ members

もう一つの利点TwoSteps 実行は、我々が止めることができるということです
簡単にnewTail は常に利用可能です.
次のステップは利用できません.私はそれをunsafechenと言う必要はありません.

各実装からの

今、それを選択する時間ですK 与えられた選択から.
そして、これは一般的なヘルパー関数であることがわかりました.

組み合わせ

combinationsWith :: ([a] -> [[[a]]]) -> [a] -> Int -> Int -> [[a]]
combinationsWith allComboGroupedFunc ms n1@selectFrom n2@selectTo =
  let
    ( isFlipped, n1', n2' ) = -- smaller value first
      if n1 < n2 then ( False
                      , max n1 0
                      , max n2 0)
      else            ( True
                      , max n2 0
                      , max n1 0)
      -- and ensure all range value are zero or positive by usig `max`
    rangeLength = n2' - n1' + 1
    reverseIfNeeded
      | isFlipped = reverse
      | otherwise = id

  in
    -- note: read from the bottom
    concat                      -- 4. final flattening
    . reverseIfNeeded           -- 3. if user put opposite way, reverse it.
    . take rangeLength          -- 2. takes only interested lists
    . drop (pred n1')           -- 1. ignore some
    $ allComboGroupedFunc ms

すべてのvariantの組み合わせは以下のようになります.

combinationsWithScanl      = combinationsWith allCombinationsWithScanlGrouped
combinationsWithSingleStep = combinationsWith unsafe_allCombinationsWithSingleStepGrouped
combinationsWithTwoSteps   = combinationsWith allCombinationsWithTwoStepsGrouped

ベンチマーク

あなたはベンチマークコードを見つけることができますmy github repository .
あなたの時間を節約する.THIS
私のベンチマーク結果の1つです.

デフォルトの組み合わせと組み合わせを選択

ベンチマーキング後AllcombinationsWithTwoSteps 最良結果
それらの中のすべてのカテゴリ(小、中、大)で.

allCombinations = allCombinationsWithTwoSteps
combinations = combinationsWithTwoSteps