{- |
Description: List monad
Copyright: Copyright (C) 2022 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P77" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P77 (randomWalkPaths) where

-- | Returns all the one-dimensional random walk paths with \(n\) steps
-- starting from position 0.
randomWalkPaths :: Int -> [[Int]]
randomWalkPaths :: Int -> [[Int]]
randomWalkPaths Int
n = ([Int] -> [Int]) -> [[Int]] -> [[Int]]
forall a b. (a -> b) -> [a] -> [b]
map [Int] -> [Int]
forall a. [a] -> [a]
reverse ([[Int]] -> [[Int]]) -> [[Int]] -> [[Int]]
forall a b. (a -> b) -> a -> b
$ Int -> [[Int]]
randomWalkPaths' Int
n

-- Returns the random walk paths, except the paths are in reverse order.
randomWalkPaths' :: Int -> [[Int]]
randomWalkPaths' :: Int -> [[Int]]
randomWalkPaths' Int
0 = [[Int
0]]
randomWalkPaths' Int
n = do
  [Int]
path <- Int -> [[Int]]
randomWalkPaths' (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
  Int
step <- [-Int
1,Int
0,Int
1]
  let path' :: [Int]
path' = [Int] -> Int -> [Int]
forall {a}. Num a => [a] -> a -> [a]
extend [Int]
path Int
step
  [Int] -> [[Int]]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [Int]
path'
  where extend :: [a] -> a -> [a]
extend []       a
_ = []
        extend xs :: [a]
xs@(a
x:[a]
_) a
s = (a
xa -> a -> a
forall a. Num a => a -> a -> a
+a
s)a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs