Haskell - 有没有更好的方法在列表上均匀分布元素

Question

给出这样的矩阵

matrix_table =

[[ 0, 0, 0, 0]
,[ 0, 0, 0, 0]
,[ 0, 0, 0, 0]
,[ 0, 0, 0, 0]
]

和列表position_list = [2, 3, 2, 10]

函数的输出

distribute_ones :: [[Int]] -> [Int] -> [[Int]]
distribute_ones matrix_table position_list 

应该是这样的

[[ 0, 1, 0, 1] -- 2 '1's in the list
,[ 0, 1, 1, 1] -- 3 '1's in the list
,[ 0, 1, 0, 1] -- 2 '1's in the list
,[ 1, 1, 1, 1] -- Since 10 > 4, all '1's in the list
]

---

我尝试了什么：

我生成了列表列表，基本矩阵

 replicate 4 (replicate 4 0)

然后将来自chunksOf库的Data.List.Split分成内部列表，以制作4 - (position_list !! nth)的切口。

最后像1一样追加和连接

take 4 . concat . map (1 :)

虽然我认为这不是最好的方法。有没有更好的方法呢？

Answer 1

为了均匀分布元素，我推荐Bjorklund的算法。 Bjorklund的算法需要两个序列来合并，并重复：

1. 尽可能合并两者的前缀，然后从每个中取出一个
2. 递归调用自身，将合并的元素作为一个序列，将较长的输入中的剩余部分作为另一个序列。

在代码中：

bjorklund :: [[a]] -> [[a]] -> [a]
bjorklund xs ys = case zipMerge xs ys of
    ([], leftovers) -> concat leftovers
    (merged, leftovers) -> bjorklund merged leftovers

zipMerge :: [[a]] -> [[a]] -> ([[a]], [[a]])
zipMerge [] ys = ([], ys)
zipMerge xs [] = ([], xs)
zipMerge (x:xs) (y:ys) = ((x++y):merged, leftovers) where
    ~(merged, leftovers) = zipMerge xs ys

以下是ghci中的一些示例：

> bjorklund (replicate 2 [1]) (replicate 2 [0])
[1,0,1,0]
> bjorklund (replicate 5 [1]) (replicate 8 [0])
[1,0,0,1,0,1,0,0,1,0,0,1,0]

如果你愿意，你可以编写一个小包装器，它只接受你关心的参数。

ones len numOnes = bjorklund
    (replicate ((-) len numOnes) [0])
    (replicate (min len numOnes) [1])

在ghci：

> map (ones 4) [2,3,2,10]
[[0,1,0,1],[0,1,1,1],[0,1,0,1],[1,1,1,1]]

Answer 2

这是另一种算法，可以在单行内的itemCount单元格中分发rowLength项目。将currentCount初始化为0.然后对于每个单元格：

1. 将itemCount添加到currentCount。
2. 如果新的currentCount小于rowLength，请使用单元格的原始值。
3. 如果新的currentCount至少是rowLength，则减去rowLength，并将单元格的值递增1。

此算法根据您提供的输入生成您期望的输出。

我们可以将此所需的状态写为简单的数据结构：

data Distribution = Distribution { currentCount :: Int
                                 , itemCount    :: Int
                                 , rowLength    :: Int
                                 } deriving (Eq, Show)

在算法的每一步，我们都需要知道我们是在发出一个输出（并递增该值），以及下一个状态值是什么。

nextCount :: Distribution -> Int
nextCount d = currentCount d + itemCount d

willEmit :: Distribution -> Bool
willEmit d = (nextCount d) >= (rowLength d)

nextDistribution :: Distribution -> Distribution
nextDistribution d = d { currentCount = (nextCount d) `mod` (rowLength d) }

为了将其保持为运行状态，我们可以将其打包在the State monad中。然后我们可以将上面的“for each cell”列表编写为单个函数：

distributeCell :: Int -> State Distribution Int
distributeCell x = do
  emit <- gets willEmit
  modify nextDistribution
  return $ if emit then x + 1 else x

要在整行上运行它，我们可以使用标准库中的traverse函数。这需要某种“容器”和一个将单个值映射到monadic结果的函数，并在同一个monad中创建结果的“容器”。这里的“容器”类型是[a]，“monad”类型是State Distribution a，所以traverse的专用类型签名是

traverse :: (Int -> State Distribution Int)
         -> [Int]
         -> State Distribution [Int]

我们实际上并不关心最终状态，我们只是希望得到的[Int]，这就是evalState所做的。这会产生：

distributeRow :: [Int] -> Int -> [Int]
distributeRow row count =
  evalState
  (traverse distributeCell row :: State Distribution [Int])
  (Distribution 0 count (length row))

将此应用于整个矩阵是zipWith的简单应用（给定两个列表和一个函数，使用两个列表中的项对重复调用该函数，返回结果列表）：

distributeOnes :: [[Int]] -> [Int] -> [[Int]]
distributeOnes = zipWith distributeRow