コラッツ予想がとけたらいいな2

自分の考察を書いていきます。

すごいFizzBuzz

Egison Haskell Idris

すごいFizzBuzzがあったので紹介します。

let (m ~> str) x = str <$ guard (x `mod` m == 0)
in map (fromMaybe . show <*> 3 ~> "fizz" <> 5 ~> "buzz")

何が何だかさっぱりですね！
これだけの機能を使っています。

1行目
・ ~>内のMaybeオルタナティブ（モノイド+アプリカティブ）でguard
・ ~>内のMaybeファンクターで(<$)

2行目
・ 関数モノイド
・ Maybeモノイド
・ []（String）モノイド
・ 関数アプリカティブの<*>

また、依存型のFizzBuzzもあります。

.
.

一方Egisonはパターンマッチを使った。

fizzbuzz' =
  matchLambda as mod(15)
    | 0                   -> "FizzBuzz"
    | (3 or 6 or 9 or 12) -> "Fizz"
    | (5 or 10)           -> "Buzz"
    | $x                  -> x

.
.

foldl, foldrを元にした、蓄積変数付き、脱出可能なloop関数　その2

Haskell

前記事：

参考記事：

継続モナドCont r aを使うようにした。

myLoop :: (accT -> a -> (accT -> b) -> b) -> (accT -> b) -> accT -> [a] -> b
--       ↓
-- 引数の順番を変える
--       ↓
myLoop :: (accT -> a -> (accT -> b) -> b) -> accT -> [a] -> (accT -> b) -> b
--       ↓
-- type Cont r a = (a -> r) -> r
--       ↓
myLoop ::                          (accT -> a -> Cont b accT) -> accT -> [a] -> Cont b accT
--       ↓
foldlM :: (Foldable t, Monad m) => (b ->    a -> m    b     ) -> b    -> t a -> m    b

「おめでとう！myLoopはfoldrContにしんかした！」
mapContがあるのだからfoldrContがあっても良いと思う。

色々やってたら、foldlCont = foldlM一発で出来た。
そしてfoldlMはfoldrで定義されている。
一周回って戻ってきた感じだ。

.
.

foldl, foldrを元にした、蓄積変数付き、脱出可能なloop関数

Haskell

簡単なfoldl

簡単なfoldlの計算から。

Prelude> foldl (-) 1 [2, 3, 4]
-8
Prelude> foldl (-) 1 [2, 3, 4, 5, 6]
-19

問題

次の問題を考えてみる。

初期値1に対し、2, 3, 4, ... を順にマイナスしていく。
累積値が-5以下になったところで、その累積値を出力せよ。

こうやるとどうだろう。

Prelude> foldl (\x y -> if x <= -5 then x else x - y) 1 [2, 3, 4, 5, 6]
-8

答えは合っているけれど、リストの末尾まで計算を続けている。
foldlは計算を途中でやめられないのだ。

参考記事を元に実装

.
.

これらの参考記事のコードをアレンジして、脱出可能なループ関数myLoopを作ってみた。

myLoopの、

  • 基底部はfoldlに似ている。
  • 再帰部はfoldrに似ている。

これで、計算途中で脱出できるようになった。

.
.

19/06/09追記

この中のどれか、なのかなあ。

.
.

Lensでリストのリストにset

Haskell

HaskellでLensをやっている。
Lensとは、タプルやリストやレコードに対しgetterやsetterを提供するものだ。

参考記事：

リストのリストに対してsetするのは、以下みたいだ。

Microsoft Windows [Version 10.0.17134.706]
(c) 2018 Microsoft Corporation. All rights reserved.

C:\me\Haskell>stack install lens --resolver lts
Selected resolver: lts-13.23

C:\me\Haskell>stack exec ghci --resolver lts
Selected resolver: lts-13.23
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude> :m Control.Lens Control.Arrow
Prelude Control.Lens Control.Arrow> [[1,2,3],[4,5,6],[7,8,9]] & (ix 0 <<< ix 1) .~ 55
[[1,55,3],[4,5,6],[7,8,9]]
Prelude Control.Lens Control.Arrow>

.
.

Idrisでラムゼーの有名なやつ、リベンジ

Idris

出来たので上げます。
定理証明はあきらめて、計算で示すことにした。

完全6点グラフK6の15本の辺から、任意の3本を選ぶ。（comb）
これにmap allとanyをかます。

メイン関数ramseyは、引数をそのまま渡すもの（赤い三角形）と、
引数をnotして渡すもの（青い三角形）との論理和を取る。

ビルドして実行すると、Trueの海が生成される。

まあでも、このラムゼーのやつに関しては、
直感的に実装できたEgisonに軍配かな。

.
.

8パズルは181440通り by Egison, Haskell

Egison Haskell

8パズルとは、いわゆるスライドパズルだ。15パズルが一般的だ。
これを題材にして、Egisonでツリーのプログラミングに挑戦してみた。
公式のデモでも、ツリーを扱っている。

8パズルの有効パターンは何通りあるかを計算しようと思う。

方法1

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

まずは3パズルで計算して、その後8パズルを計算した。
3パズルの全パターンは12だった。

……
6時間実行しても終わらなかった。
bugが発覚した。直せなかった。
（bugのせいで計算が終わらないのかは分からないけれど）

方法2

8パズルの全パターンは、9!=362880より小さい。それは分かる。
9!から、8パズルのルールで辿り着ける物をフィルタリングすれば良いのではないか。

以下の方法を使ってみよう。

参考記事：

定理：s に対応する状態からはじめたとき，
8パズルが完成できる ⟺ s を t にする置換のパリティ（偶奇）と「空き」の最短距離の偶奇が等しい。

置換のパリティを求めるには、
置換で1から順番にそろえていけば良いそうだ。

最初Egisonでやっていたけれど、計算が終わらないのでHaskellにした。
出来たプログラムはこちら。（ツリー使わなかったよ……）

8パズルの有効なパターンは、181440ということが分かった。
9!/2なのは偶然ではないのだろう。

おまけ

群論の言葉で言うと、以下になりそうだ。

スライドパズル群は、集合permutations [1..9]を、二つの軌道に二等分する。
一つは[1, 2, 3, 4, 5, 6, 7, 8, 9]を元に持つ軌道。
もう一つは[1, 2, 3, 4, 5, 6, 8, 7, 9]を元に持つ軌道。

.
.