ninetynine-1.3.0: Ninety-Nine Haskell Problems
CopyrightCopyright (C) 2022 Yoo Chung
LicenseGPL-3.0-or-later
Maintainerdev@chungyc.org
Safe HaskellSafe-Inferred
LanguageGHC2021

Problems.P77

Description

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P77.

Synopsis

Documentation

randomWalkPaths :: Int -> [[Int]] Source #

A list is also a monad.

For example, dupli in 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

Expand

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]