{- | Description: List monad Copyright: Copyright (C) 2022 Yoo Chung License: GPL-3.0-or-later Maintainer: dev@chungyc.org Part of Ninety-Nine Haskell "Problems". Some solutions are in "Solutions.P77". -} module Problems.P77 (randomWalkPaths) where import qualified Solutions.P77 as Solution -- $setup -- >>> import Data.List (sort) {- | A list is also a monad. For example, 'Problems.P14.dupli' in 'Problems.P14' could have been implemented with the list monad: >>> :{ let dupli xs = do x <- xs [x, x] in dupli [1, 2, 3] :} [1,1,2,2,3,3] Using the list monad, implement a function which returns all the one-dimensional random walk paths with \(n\) steps. Starting from position 0, each step can change positions by -1, 0, or 1. Each path will be a list of positions starting from 0. === Examples >>> randomWalkPaths 0 [[0]] >>> sort $ randomWalkPaths 2 [[0,-1,-2],[0,-1,-1],[0,-1,0],[0,0,-1],[0,0,0],[0,0,1],[0,1,0],[0,1,1],[0,1,2]] === __Hint__ The list monad can be a simple way to model non-deterministic computations. For example, if we have one number that may be either 2 or 3, and we want to multiply it by another number that may be either 5 or 6, we can get the possible results as follows: >>> :{ do x <- [2,3] :: [Int] y <- [5,6] :: [Int] return $ x*y :} [10,12,15,18] -} randomWalkPaths :: Int -> [[Int]] randomWalkPaths :: Int -> [[Int]] randomWalkPaths = Int -> [[Int]] Solution.randomWalkPaths