Dynamic List Comprehension in Haskell

Question

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

(I thought possible, although cumbersome and limited, to write out a larger list comprehension to start with and trim it by adding to s a parameter and helper functions that could make one or more of the elements a value that could easily be filtered later, and the associated conditions True by default.)

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

Answer 1

The question is incredibly difficult to understand.

Is there a way to (conveniently) program the number of elements and their associated conditions based on an earlier computation?

The problem is "program" is not really an understandable verb in this sentence, because a human programs a computer, or programs a VCR, but you can't "program a number". So I don't understand what you are trying to say here.

But I can give you code review, and maybe through code review I can understand the question you are asking.

Unsolicited code review

It sounds like you are trying to solve a maze by eliminating dead ends, maybe.

What your code actually does is:

1. Generate a list of cells that are not dead ends or adjacent to dead ends, called filtered

2. Generate a sequence of adjacent cells from step 1, sequences

3. Concatenate four such adjacent sequences into a route.

Major problem: this only works if a correct route is exactly eight tiles long! Try to solve this maze:

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

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

How do I generate a list if I don't know how long it is beforehand?

Solutions

You can solve a maze with a search (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 function solve works by depth-first search. Rather than putting everything in a single list comprehension, it works recursively.

1. In order to find a path from start to end, if start /= end,

2. Look at all cells adjacent to the end, neighbor <- maze end,

3. Make sure that we're not backtracking over a cell guard (negihbor `notElem` path),

4. Try to find a path from start to neighbor.

Don't try to understand the whole function at once, just understand the bit about recursion.

Summary

If you want to find the route from cell 0 to cell 19, recurse: We know that cell 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

The guard,

someCondition a == True

Is equivalent to,

someCondition a

And therefore also equivalent to,

(someCondition a == True) == True

Or,

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

Or,

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

The first one, someCondition a, is fine.

Footnote about do notation

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

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

The equivalent code in list comprehension syntax is,

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

Answer 2

Is there a way to (conveniently) program the number of elements and their associated conditions based on an earlier computation? For example, return type [[a,b,c]] or [[a,b,c,d,e]] depending on another value in the program?

I suppose you want to encode the length of the list (or vector) statically in the type signature. Length of the standard lists cannot be checked on type level.

One approach to do that is to use phantom types, and introduce dummy data types which 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 length which will have distinct types:

vector2d :: Float -> Float -> Vector D2
vector2d x y = Vector $ listArray (1,2) [x,y]

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

If the length of the output depends on the length of the input, then consider using type-level arithmetics to parametrize the output. You can find more by googling for "Haskell statically sized vectors".

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

Answer 3

Looks like you're trying to solve some logic puzzle by unique selection from finite domain. Consult these:

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

The way this helps us is, we carry our domain around while we're making picks from it; and the next pick is made from the narrowed domain containing what's left after the previous pick, so a chain is naturally formed. E.g.

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, i.e. 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 a number of elements in your answer as a part of your list comprehension:

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

or just create different answers based on a condition,

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

Answer 4

You have Data.List.subsequences

You can write your list comprehension in monadic form (see guards in Monad Comprehensions):

(Explanation: The monad must be an instance of MonadPlus which supports failure.

guard False makes the monad fail evaluating to mzero., subsequent results are appended with 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, obtaining elements recursively, saving 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 non trivial result:

    [2,3]
    [3,2]