💫
ドドスコ in PureScript
Ref: https://twitter.com/Sheeeeepla/status/1554028833942441984
面白い問題だと思ったのでぽく書きたかった
ドドスコード
module Main where
import Prelude
import Control.Monad.Rec.Class (Step(..), tailRecM)
import Data.List (List, length, reverse, (:), take)
import Data.List as List
import Effect (Effect)
import Effect.Console (log)
import Effect.Random (randomBool)
data Dodosuko = Dodo | Suko
derive instance Eq Dodosuko
instance showDodosuko :: Show Dodosuko where
show Dodo = "ドド"
show Suko = "スコ"
ranDodosuko :: Effect Dodosuko
ranDodosuko = randomBool <#> if _ then Dodo else Suko
endodosukoList :: List Dodosuko
endodosukoList = reverse $ List.fromFoldable $ [ Dodo, Suko, Suko, Suko, Dodo, Suko, Suko, Suko, Dodo, Suko, Suko, Suko ]
endodosukoListLength :: Int
endodosukoListLength = length endodosukoList
dodoskoRec :: List Dodosuko -> Effect (Step (List Dodosuko) Unit)
dodoskoRec prevDodosukoList =
if take endodosukoListLength prevDodosukoList == endodosukoList then do
log "ラブ注入♡"
pure $ Done unit
else do
newDodosuko <- ranDodosuko
log $ show newDodosuko
pure $ Loop $ newDodosuko : prevDodosukoList
main :: Effect Unit
main = tailRecM dodoskoRec $ List.fromFoldable []
List
PureScript では配列として Array
を使うのが一般的ですが、List
という先頭へ要素を追加する操作 :
が O(1) である永続化可能なデータ型があります (Haskell ではこちらを一般的に使う)
ドドスコを Array
に貯めていくと配列の長さに比例して追加操作が遅くなっていきますが、ここで List
を使う事で全体での計算量を O(N) にしています。(N はドドスコの長さの期待値)
ただし List
は前に要素が増えていくので endodosukoList
の中身は reverse
で反転させています
MonadRec
PureScript で再帰をすると必ずと言っていいほど Maximum call stack size exceeded
が起きてしまいますが、MonadRec
クラスないし tailRecM
関数を使うとそれを回避できます。
なんかの関数を渡して、それが Done なにかしら
を返すとループが終了し、Loop なにかしら
を返すともう一回その関数を実行してくれます。Effect
は MonadRec
のインスタンスなのでこれが可能です。
おまけ
これは tailRecM
を使わなかったときの、Maximum call stack size exceeded スコ
Discussion