『8パズルは181440通り』をegison-haskellで

前記事：

8パズルは181440通り、というのをどうしてもツリーを使って計算したかった。
方法は以下。

ツリーのルートを、揃ったパターンとする。
それを、下に向かって成長させていく。追加するのは一手動かしたパターンだ。
同じパターンの所は止める。
ツリーの成長が止まったら、全パターン網羅完了だ。

egison-haskellでやってみた。
同じパターンのチェックに、Stateモナドを使ってみた。
egison-haskellのmatchの中でdoとか使えるのだ。
32回nextTreeをかまして、181440通りを出力できた。
GHCiで2時間半ぐらいかかった。

コード（一部）

nextTree :: State [[Int]] (Tree [Int]) -> State [[Int]] (Tree [Int])
nextTree sTree = do
  tr <- sTree
  match tr (tree integer) $
    [mc| nodePat $tree1 $x $tree2 $tree3 $tree4 =>
      do
        if tree1 == Leaf && tree2 == Leaf && tree3 == Leaf && tree4 == Leaf
          then do -- 最下層なので、状態に無ければ、ツリーを伸ばす
            xs <- get
            if elem x xs
              then return $ Node Leaf x Leaf Leaf Leaf
              else do
                put $ xs ++ [x]
                return $ nextEight x
          else do
            ret1 <- nextTree $ state (\s -> (tree1, s))
            ret2 <- nextTree $ state (\s -> (tree2, s))
            ret3 <- nextTree $ state (\s -> (tree3, s))
            ret4 <- nextTree $ state (\s -> (tree4, s))
            return $ Node ret1 x ret2 ret3 ret4
    |] .*.
    [mc| leafPat => return Leaf |] .*. PNil

initTreeE :: Tree [Int]
initTreeE = Node Leaf [1, 2, 3, 4, 5, 6, 7, 8, 9] Leaf Leaf Leaf

実行結果

Microsoft Windows [Version 10.0.18362.356]
(c) 2019 Microsoft Corporation. All rights reserved.

C:\me\Haskell>cd egison-haskell

C:\me\Haskell\egison-haskell>stack ghci
Configuring GHCi with the following packages: egison-haskell
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
[1 of 5] Compiling Control.Egison.Core ( C:\\me\Haskell\egison-haskell\src\Control\Egison\Core.hs, interpreted )
[2 of 5] Compiling Control.Egison.Match ( C:\\me\Haskell\egison-haskell\src\Control\Egison\Match.hs, interpreted )
[3 of 5] Compiling Control.Egison.QQ ( C:\\me\Haskell\egison-haskell\src\Control\Egison\QQ.hs, interpreted )
[4 of 5] Compiling Control.Egison.Matcher ( C:\\me\Haskell\egison-haskell\src\Control\Egison\Matcher.hs, interpreted )
[5 of 5] Compiling Control.Egison   ( C:\\me\Haskell\egison-haskell\src\Control\Egison.hs, interpreted )
Ok, five modules loaded.
Loaded GHCi configuration from C:\\Users\\furuta5\\AppData\\Local\\Temp\\haskell-stack-ghci\\57aa0b51\\ghci-script   
*Control.Egison.QQ Control.Egison Control.Egison.Core Control.Egison.Match Control.Egison.Matcher Control.Egison.QQ> :l sample/MyTree
[1 of 6] Compiling Control.Egison.Core ( C:\\me\Haskell\egison-haskell\src\Control\Egison\Core.hs, interpreted )
[2 of 6] Compiling Control.Egison.Match ( C:\\me\Haskell\egison-haskell\src\Control\Egison\Match.hs, interpreted )
[3 of 6] Compiling Control.Egison.QQ ( C:\\me\Haskell\egison-haskell\src\Control\Egison\QQ.hs, interpreted )
[4 of 6] Compiling Control.Egison.Matcher ( C:\\me\Haskell\egison-haskell\src\Control\Egison\Matcher.hs, interpreted )
[5 of 6] Compiling Control.Egison   ( C:\\me\Haskell\egison-haskell\src\Control\Egison.hs, interpreted )
[6 of 6] Compiling MyTree           ( sample\MyTree.hs, interpreted )
Ok, six modules loaded.
*MyTree> :set +s         
*MyTree> length $ execState (convergence nextTree (state (\s -> (initTreeE, s))) 30) []
181217
(6331.84 secs, 1,014,170,890,048 bytes)
*MyTree> length $ execState (convergence nextTree (state (\s -> (initTreeE, s))) 31) []
181438
(7224.78 secs, 1,029,393,531,712 bytes)
*MyTree> length $ execState (convergence nextTree (state (\s -> (initTreeE, s))) 32) []
181440★完了
(8500.22 secs,★2時間半ぐらい 1,042,774,783,832 bytes)
*MyTree> length $ execState (convergence nextTree (state (\s -> (initTreeE, s))) 33) []
181440★増えてない
(9760.77 secs,★3時間弱 1,056,135,757,704 bytes)