6

我决定学习 Haskell 并学习以更实用的方式思考，所以我试图解决非常简单的练习，尝试在这个范式中使用一个好的方法。

我正在尝试在 Haskell 中实现这个简单的练习：

Input: [2, 4, 1, 1, 2]
Output: [True, True, False, False, False, False, True, False, True, True]

因此，列表中的元素将 Input落入列表中，奇数元素将是; 对于每一个重复列表中的值所指示的次数。FalseOutputTrueInput

遍历Input列表，如果i  ᵗʰ 项在 pair 位置，则追加到输出True i次 to Output；如果 i  ᵗʰ 项目位于奇数位置，则将False i次附加到Output列表中。

这似乎是一个非常简单的问题，而且确实如此。但对我来说，没有任何函数式编程背景，我不知道如何用 Haskell 来表达。

我试图通过在列表理解中使用 λ 函数来跟踪当前索引。

    row :: [Integer] -> [Bool]
    row xs = [ (last $ zipWith (\i x -> x) [1..] [0..i]) `mod` 2 == 0
                | j <- xs, i <- [0..j-1] ]

但我不了解它的行为，所以我最终将findIndices 其用作快速替代方案：

    row :: [Integer] -> [Bool]
    row xs = [ (head $ findIndices (==j) (xs)) `mod` 2 == 0
                | j <- xs, i <- [0..j-1] ]

使用最后一种方法似乎没问题：

    > let xs = [ 1, 4, 3, 2 ]
    > print $ row xs
    [True,False,False,False,False,True,True,True,False,False]

但问题并没有解决，因为项目不一定是唯一的：

    > let xs = [ 2, 2, 4, 3]
    > print $ row xs
    [True,True,True,True,True,True,True,True,False,False,False]

因为head findIndices只给出了第一次出现的情况。（虽然我认为，如果有效，那不是解决这个问题的一种非常有效的方法。）

如何以Haskellian方式实现我正在寻找的结果？

4

6 回答 6

11

您希望将输入列表中的每个元素转换Bool为与元素所说的一样多的相等 s的序列，并且如果输入列表中的数字的索引是偶数，并且索引是奇数，那么您想要Boolbe 。TrueFalse

为此，您不需要索引，最好避免使用它 - 这样可以提供更简单且通常更有效的代码。关键是值是交替的，它有一个周期性的模式。为了构建这样的周期性模式，Prelude 提供了有用的

cycle :: [a] -> [a]

Prelude> take 10 $ cycle [1,2,3]
[1,2,3,1,2,3,1,2,3,1]
Prelude> take 10 $ cycle [True,False]
[True,False,True,False,True,False,True,False,True,False]

整洁，这正是我们需要的。

现在，我们可以将输入列表的每个元素与相应的 配对Bool：

[  2,    2,   4,   3]
[True,False,True,False,...

我们可以zip用来产生对，[(2,True), (2,False), ...]然后使用一个函数将这个对转换为适当的Bools 序列。

但是这种模式是如此普遍，以至于我们有一个特殊的高阶函数，zipWith.

所以如果列表元素的类型是Int，我们可以写

row :: [Int] -> [Bool]
row xs = concat $ zipWith replicate xs (cycle [True,False])

对于 type Integer，我们不能使用replicate，但可以使用genericReplicatefrom Data.List。

于 2013-05-31T21:43:43.923 回答
2

看来您已经发现可以使用zip将元素与其索引配对。对于每个索引i和相应的元素n，您想要生成n一个布尔值的副本（带有replicate），这个布尔值取决于i是奇数还是偶数。这意味着将map每个元组 ping(i, n)到一个布尔值列表，因此您会得到一个列表列表 ( [[Bool]])。最后一步是将这些列表与concat（可以与mapinto结合使用concatMap）合并。

row = concatMap (\(i, n) -> replicate n (odd i)) . zip [1..]

或者，如果您不喜欢 pointfree 风格：

row xs = concatMap (\(i, n) -> replicate n (odd i)) (zip [1..] xs)
于 2013-05-31T21:25:43.793 回答
1

另一种解决方案

row :: [Integer] -> [Bool]
row ns = r' True ns
    where
        r' :: Bool -> [Integer] -> [Bool]
        r' b (n:ns) = replicate b n : r' (not b) ns
        r' b   []   = []

（未测试）

于 2013-05-31T21:30:42.933 回答
1 
row :: [Integer] -> [Bool]
row xs = row' xs True

row' [] _ = []
row' (x:xs) b = (replicate x b) ++ (row' xs (not b))
于 2013-05-31T21:41:48.957 回答
0

我解释

遍历Input列表，如果iᵗʰ项在pair位置，则追加到输出True i次到Output；如果 i ᵗʰ 项目位于奇数位置，则将 False i 次附加到输出列表。

我看到了两种解释这一点的方法。“对于所有元素，如果第 i 个元素是偶数，则返回 True i 次。否则，返回 false i 次”或“对于所有元素，包含 (v :: Int) 的第 i 个元素应返回 True v 次，如果如果 i 是奇数，则 i 是偶数或 False v 次”。第二个已经有一个令人满意的答案，所以我会给第一个。

有些人喜欢参考指数，但在这种情况下，您无需担心指数。您可以确定有多少Bools 而无需计算您遍历了多少元素。

accum f (x:[]) = [x]
accum f (x:xs) = (x):(map f (accum f xs))

这个函数接受一个函数f和一个列表。它适用f于除第一个元素之外的每个元素，然后对列表的尾部进行递归调用，这再次适用f于每个剩余元素，等等......结果是这样的：

accum (+1) [1,1,1,1,1]
[2,3,4,5,6]

该函数+1对第二个元素应用两次，对第二个元素应用三次，等等。现在这对我们有什么帮助？那么我们可以这样做：

accum (\x -> [head x] ++ x) $ map (\x -> [x]) [2, 4, 1, 1, 2]
[[2],[4,4],[1,1,1],[1,1,1,1],[2,2,2,2,2]]

我们首先将每个元素转换为一个包含单个项目的列表。weaccum与您在上面看到的 lambda，它将头部连接到列表。我们现在可以直接转换为Bools 而无需进一步操作。

(map . map) odd $ accum (\x -> [head x] ++ x) $ map (\x -> [x]) [2, 4, 1, 1, 2]
[[False],[False,False],[True,True,True],[True,True,True,True],[False,False,False,False,False]]

你想要[Bool]的并没有[[Bool]]那么简单concat。请注意，您可以concat先使用，然后使用map代替map . map：

map odd $ concat $ accum (\x -> [head x] ++ x) $ map (\x -> [x]) [2, 4, 1, 1, 2]
于 2013-06-01T04:45:21.017 回答
0

这是我将如何做到这一点。

row [] = []
row xs = row' xs 0
   where row' xs i
            | i >= length xs    = []
            | otherwise         = (take (xs !! i) (repeat (isOdd i))) ++ (row' xs (i+1))


isOdd n = n `rem` 2 == 1

但是我在这台计算机上没有 ghc 来测试它。

于 2013-05-31T21:13:36.243 回答