Understanding a dynamic list in Haskell

Question

Suppose I have a list comprehension that returns a list of sequences where the selected items depend on each other (see example below). Is there a (convenient) way to program the number of elements and related conditions based on an earlier calculation? For example, does the return type [[a, b, c]] or [[a, b, c, d, e]] depend on another value in the program? Also, are there other / better ways than list comprehension to formulate the same idea?

(I considered it possible, albeit cumbersome and limited, to write out a broader understanding of the list in order to start with it and trim it, adding to s an option and auxiliary functions that could make one or more of the elements that can be easily filtered out later, and associated True conditions by default.)

s = [[a, b, c, d] | a <- list, someCondition a, b <- list, b /= a, not (someCondition b), otherCondition ab, c <- list, c /= a, c /= b, not (someCondition c), otherCondition bc, d <- list, d /= a, d /= b, d /= c, someCondition d, someCondition (last d), otherCondition cd] 

Answer 1

It seems that you are trying to solve some kind of logic puzzle by a unique choice from the final domain. Consult with them:

• Euler 43 - is there a monad to help comprehend this list?
• Splitting a list into a list of possible tuples

How it helps us, we carried our domain while we make a choice from it; and the next selection is made from a narrowed region containing what remains of the previous selection, so that the chain is naturally formed. For instance.

 p43 = sum [ fromDigits [v0,v1,v2,v3,v4,v5,v6,v7,v8,v9] | (dom5,v5) <- one_of [0,5] [0..9] -- [0..9] is the , (dom6,v6) <- pick_any dom5 -- initial domain , (dom7,v7) <- pick_any dom6 , rem (100*d5+10*d6+d7) 11 == 0 .... -- all possibilities of picking one elt from a domain pick_any :: [a] -> [([a], a)] pick_any [] = [] pick_any (x:xs) = (xs,x) : [ (x:dom,y) | (dom,y) <- pick_any xs] -- all possibilities of picking one of provided elts from a domain -- (assume unique domains, ie no repetitions) one_of :: (Eq a) => [a] -> [a] -> [([a], a)] one_of ns xs = [ (ys,y) | let choices = pick_any xs, n <- ns, (ys,y) <- take 1 $ filter ((==n).snd) choices ] 

---

You can trivially check the number of elements in your answer as part of your understanding of the list:

 s = [answer | a <- .... , let answer=[....] , length answer==4 ] 

or just create different answers based on the condition,

 s = [answer | a <- .... , let answer=if condition then [a,b,c] else [a]] 

Answer 2

The question is incredibly hard to understand.

Is there a (convenient) way to program the number of elements and related conditions based on an earlier calculation?

The problem “program” is not really an understandable verb in this sentence, because a person is programming a computer or programming a VCR, but you cannot “program a number”. Therefore, I do not understand what you are trying to say here.

But I can give you an overview of the code, and perhaps through the code review I can understand the question you are asking.

View unsolicited code

It looks like you are trying to solve the maze, possibly eliminating the dead ends.

Actually your code:

• Create a list of cells that are not dead or adjacent to dead ends called filtered

• Create a sequence of neighboring cells from step 1, sequences

• Combining four such adjacent sequences into a route.

The main problem : this only works if the correct route is exactly eight fragments! Try to solve this maze:

  [E] - [] - [] - [] 
              |
 [] - [] - [] - []
  |
 [] - [] - [] - []
              |
 [] - [] - [] - []
  |
 [] - [] - [] - [E]

So, working backwards from the code review, it looks like your question is:

How do I generate a list if I do not know how much time has passed?

Decision

You can solve the maze by searching (DFS, BFS, A *).

 import Control.Monad -- | Maze cells are identified by integers type Cell = Int -- | A maze is a map from cells to adjacent cells type Maze = Cell -> [Cell] maze :: Maze maze = ([[1], [0,2,5], [1,3], [2], [5], [4,6,1,9], [5,7], [6,11], [12], [5,13], [9], [7,15], [8,16], [14,9,17], [13,15], [14,11], [12,17], [13,16,18], [17,19], [18]] !!) -- | Find paths from the given start to the end solve :: Maze -> Cell -> Cell -> [[Cell]] solve maze start = solve' [] where solve' path end = let path' = end : path in if start == end then return path' else do neighbor <- maze end guard (neighbor `notElem` path) solve' path' neighbor 

The solve function works by searching in depth. Instead of putting everything in a single list comprehension, it works recursively.

• To find the path from start to end , if start /= end ,

• Look at all the cells near the end, neighbor <- maze end ,

• Make sure we are not backing away from the guard (negihbor `notElem` path) cell guard (negihbor `notElem` path) ,

• Try to find a path from start to neighbor .

Do not try to understand the whole function at once, just understand the bit about recursion.

Summary

If you want to find a route from cell 0 to cell 19, recurse: we know that cells 18 and 19 are connected (because they are directly connected), so we can instead try to solve the problem of finding a route from cell 0 to cell 18.

This is recursion.

Footnotes

Defender

 someCondition a == True 

Is equivalent

 someCondition a 

And therefore also equivalent

 (someCondition a == True) == True 

Or

 (someCondition a == (True == True)) == (True == (True == True)) 

Or

 someCondition a == (someCondition a == someCondition a) 

The first, someCondition a , is good.

Footnote for do

The designation do in the above example is equivalent to list comprehension,

 do neighbor <- maze end guard (neighbor `notElem` path) solve' path' neighbor 

Equivalent code in list comprehension syntax,

 [result | neighbor <- maze end, neighbor `notElem` path, result <- solve' path' neighbor] 

Answer 3

Is there a (convenient) way to program the number of elements and related conditions based on an earlier calculation? For example, does the return type [[a, b, c]] or [[a, b, c, d, e]] depend on another value in the program?

I assume that you want to encode the length of the list (or vector) statically in a type signature. The length of standard lists cannot be checked at the level level.

One approach to do this is to use phantom types and introduce dummy data types that will encode different sizes:

 newtype Vector d = Vector { vecArray :: UArray Int Float } -- using EmptyDataDecls extension too data D1 data D2 data D3 

Now you can create vectors of different lengths that will have different types:

 vector2d :: Float -> Float -> Vector D2 vector2d xy = Vector $ listArray (1,2) [x,y] vector3d :: Float -> Float -> Float -> Vector D3 vector3d xyz = Vector $ listArray (1,3) [x,y,z] 

If the output length depends on the input length, consider using level arithmetic at the level to parameterize the output. You can find more on googling for "Haskell Static Dimension Vectors".

A simpler solution is to use tuples that are fixed length. If your function can create either a 3-tuple or a 5-tuple, wrap them with the Either data type: `Either (a, b, c) (a, b, c, d, e).

Answer 4

You have Data.List.subsequences

You can write your understanding of the list in monadic form (see guards in Monad Comprehensions ):

(Explanation: The monad must be an instance of MonadPlus that supports rejection.

guard False causes monad fail to evaluate mzero., subsequent results are added using mplus = (++) for the list monad.)

 import Control.Monad (guard) myDomain = [1..9] -- or whatever validCombinations :: [a] -> [[a]] validCombinations domainList = do combi <- List.subsequences domainList case combi of [a,b] -> do guard (propertyA a && propertyB b) return combi [a,b,c] -> do guard (propertyA a && propertyB b && propertyC c) return combi _ -> guard False main = do forM_ (validCombinations myDomain) print 

Update again, retrieve items recursively, save combinations and checks

 import Control.Monad validCombinations :: Eq a => Int -> Int -> [a] -> [(a -> Bool)] -> [a] -> [[a]] validCombinations indx size domainList propList accum = do elt <- domainList -- try all domain elements let prop = propList!!indx guard $ prop elt -- some property guard $ elt `notElem` accum -- not repeated {- case accum of prevElt : _ -> guard $ some_combined_check_with_previous elt prevElt _ -> guard True -} if size > 1 then do -- append recursively subsequent positions other <- validCombinations (indx+1) (size-1) domainList propList (elt : accum) return $ elt : other else return [elt] myDomain = [1..3] :: [Int] myProps = repeat (>1) main = do forM_ (validCombinations 0 size myDomain myProps []) print where size = 2 

result for size 2 with nontrivial result:

  [2,3]
     [3.2]