haskell - Haskell 中的动态列表理解

Question

假设我有一个列表理解，它返回一个序列列表，其中选择的元素相互依赖（参见下面的示例）。有没有办法（方便地）根据早期计算对元素的数量及其相关条件进行编程？例如，返回类型 [[a,b,c]] 或 [[a,b,c,d,e]] 取决于程序中的另一个值？此外，除了列表理解之外，还有其他/更好的方法来制定相同的想法吗？

（我认为可能，虽然麻烦且有限，但可以编写一个更大的列表推导式开始，并通过向s添加一个参数和辅助函数来修剪它，这些参数和辅助函数可以使一个或多个元素成为以后可以轻松过滤的值，以及相关的条件默认为真。）

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]

score 4 · Accepted Answer

这个问题非常难以理解。

有没有办法（方便地）根据早期计算对元素的数量及其相关条件进行编程？

问题是“程序”在这句话中并不是一个真正可以理解的动词，因为人类对计算机进行了编程，或者对 VCR 进行了编程，但您不能“对数字进行编程”。所以我不明白你在这里想说什么。

但是我可以给你代码审查，也许通过代码审查我可以理解你提出的问题。

不请自来的代码审查

听起来您可能正在尝试通过消除死胡同来解决迷宫。

你的代码实际上做的是：

生成不是死角或与死角相邻的单元格列表，称为filtered
从步骤 1 生成一系列相邻单元格，sequences
将四个这样的相邻序列连接成一条路线。

主要问题：这只有在正确的路线正好是八格长时才有效！尝试解决这个迷宫：

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

因此，从代码审查向后工作，听起来您的问题是：

如果我事先不知道它有多长，我如何生成一个列表？

解决方案

您可以通过搜索（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

该功能solve通过深度优先搜索工作。它不是将所有内容都放在一个列表理解中，而是递归地工作。

为了找到从start到的路径end，如果start /= end，
查看与末尾相邻的所有单元格neighbor <- maze end，
确保我们没有在一个单元格上回溯guard (negihbor `notElem` path)，
尝试找到从start到的路径neighbor。

不要试图一下子理解整个函数，只要理解一点关于递归。

概括

如果要找到cell 0到cell 19的路径，递归：我们知道cell 18和cell 19是相连的（因为它们是直接相连的），所以我们可以尝试解决从cell 0到cell的路由问题单元格 18。

这是递归。

脚注

守卫，

someCondition a == True

相当于，

someCondition a

因此也等价于，

(someCondition a == True) == True

或者，

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

或者，

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

第一个，someCondition a很好。

`do`关于符号的脚注

上面例子中的do符号等价于列表推导，

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

列表理解语法中的等效代码是，

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

score 2 · Accepted Answer

有没有办法（方便地）根据早期计算对元素的数量及其相关条件进行编程？例如，返回类型 [[a,b,c]] 或 [[a,b,c,d,e]] 取决于程序中的另一个值？

我想您想在类型签名中静态编码列表（或向量）的长度。无法在类型级别检查标准列表的长度。

一种方法是使用幻像类型，并引入将编码不同大小的虚拟数据类型：

newtype Vector d = Vector { vecArray :: UArray Int Float }

-- using EmptyDataDecls extension too
data D1
data D2
data D3

现在您可以创建具有不同类型的不同长度的向量：

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]

如果输出的长度取决于输入的长度，那么考虑使用类型级算术来参数化输出。您可以通过谷歌搜索“Haskell 静态大小的向量”找到更多信息。

一个更简单的解决方案是使用固定长度的元组。如果您的函数可以生成 3 元组或 5 元组，请使用Either数据类型包装它们：`Either (a,b,c) (a,b,c,d,e)。

score 1 · Accepted Answer

看起来您正试图通过从有限域中进行唯一选择来解决一些逻辑难题。咨询这些：

这对我们有帮助的方式是，我们在从中挑选域名时随身携带；并且下一个选择是从包含上一个选择之后剩下的内容的狭窄域中进行的，因此自然形成了一条链。例如

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 ]

作为列表理解的一部分，您可以简单地检查答案中的一些元素：

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

或者只是根据条件创建不同的答案，

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

score 1 · Accepted Answer

你有Data.List.subsequences

您可以以单子形式编写列表理解（请参阅Monad Comprehensions 中的守卫）：

（说明：monad 必须是支持失败的MonadPlus的实例。

guard False使 monad 无法评估为 mzero。，后续结果将附加 mplus = (++) 用于 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

再次更新，递归获取元素，保存组合和检查

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

尺寸 2 的结果具有非平凡的结果：

    [2,3]
    [3,2]

haskell - Haskell 中的动态列表理解

4 回答 4

不请自来的代码审查

解决方案

概括

脚注

do关于符号的脚注

Related

Reference

`do`关于符号的脚注