Haskell List Monad State Dependance

Question

I have to write a program in Haskell that will solve some nondeterministic problem. I think i understand List Monad in 75% so it is oblivious choice but...

(My problem is filling n x m board with ships and water i am given sums of rows and colums every part of ship has its value etd its not important right now).

I want to guard as early as possible to make algoritm effective the problem is that possibility of insertion of ship is dependant from what i am given / what i have inserted in previus moves lets call it board state and i have no idea how to pass it cuz i can't generate a new state from board alone)

My Algoritm is: 1. Initialize First Board 2. Generate First Row trying applying every possible insertion (i can insert sheep verticaly so i need to remember to insert other parts of sheep in lower rows) 3. Solve the problem for smaller board (ofc after generating each 2 rows i check is everything ok)

But i have no idea how can I pass new states cuz as far as i have read about State Monad it generates new state from old state alone and this is impossible for me to do i would want to generate new state while doing operations on value).

I am sorry for my hatred towards Haskell but after few years of programing in imperative languages being forced to fight with those Monads to do things which in other languages i could write almost instantly makes me mad. (well other things in Haskell are fine for me and some of them are actually quite nice).

Answer 1

Combine StateT with the list monad to get your desired behavior.

Here's a simple example of using the non-determinism of the list monad while still keeping a history of previous choices made:

import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.State

fill :: StateT [Int] [] [Int]
fill = do
    history <- get
    if (length history == 3)
        then return history
        else do
            choice  <- lift [0, 1, 2]
            guard (choice `notElem` history)
            put (choice:history)
            fill

fill maintains a separate history for each path that it tries out. If it fills up the board it returns successfully, but if the current choice overlaps with a previous choice it abandons that solution and tries a different path.

You run it using evalStateT, supplying an initial empty history:

>>> evalStateT fill []
[[2,1,0],[1,2,0],[2,0,1],[0,2,1],[1,0,2],[0,1,2]]

It returns a list of all possible solutions. In this case, that just happens to be the list of all permutations in which we could have filled up the board.