Copyright | Copyright (C) 2022 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

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

## Synopsis

- randomWalkPaths :: Int -> [[Int]]

# 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

`>>>`

[[0]]`randomWalkPaths 0`

`>>>`

[[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]]`sort $ randomWalkPaths 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]`:{`