💫

ドドスコ in PureScript

に公開
PureScript
tech

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 関数を使うとそれを回避できます。

https://pursuit.purescript.org/packages/purescript-tailrec/5.0.1/docs/Control.Monad.Rec.Class

なんかの関数を渡して、それが Done なにかしら を返すとループが終了し、Loop なにかしら を返すともう一回その関数を実行してくれます。Effect は MonadRec のインスタンスなのでこれが可能です。

おまけ

これは tailRecM を使わなかったときの、Maximum call stack size exceeded スコ

GitHubで編集を提案

Discussion