haskell - 在 Haskell 中从右侧开始将列表的所有其他元素加倍

Question

我有一个列表，我想从右侧将该列表中的所有其他元素加倍。

还有另一个相关的问题可以解决这个问题，但它是从左侧翻倍，而不是从右侧翻倍：Haskell: Double every 2nd element in list

例如，在我的场景中，[1,2,3,4] 将变为 [2,2,6,4]，而在该问题中，[1,2,3,4] 将变为 [1,4,3 ,8]。

我将如何实现这一点？

Answer 1

我认为最佳答案误解了这个问题。标题清楚地表明 OP 希望将列表右侧的第二个、第四个等元素加倍。Ørjan Johansen 的回答是正确的，但速度很慢。这是我更有效的解决方案：

doubleFromRight :: [Integer] -> [Integer]
doubleFromRight xs = fst $ foldr (\x (acc, bool) ->
                                  ((if bool then 2 * x else x) : acc,
                                   not bool)) ([], False) xs

它从右侧折叠列表。初始值是一个包含空列表和布尔值的元组。布尔值以 false 开始，并且每次都翻转。仅当布尔值为真时，该值才乘以 2。

Answer 2

好的，正如@TomEllis 所提到的，其他人似乎都将您的问题解释为左侧的奇数元素，而不是您的标题所暗示的右侧的偶数元素。

由于您从右侧开始检查位置，因此在找到列表末尾之前无法知道要加倍的内容。所以解决方案不能偷懒，并且需要在返回任何东西之前将整个列表临时存储在某个地方（即使只是在执行堆栈上）。

鉴于此，最简单的解决方案可能是在左起解决方案之前和之后应用 reverse：

doubleFromRight = reverse . doubleFromLeft . reverse

Answer 3

想想看。

double = zipWith ($) (cycle [(*2),id])

编辑 我应该注意，这不是我的解决方案，它是链接帖子的解决方案，(*2)并id翻转。这就是为什么我说考虑一下，因为这是一个微不足道的解决方案。

Answer 4

好的，不像其他答案那样优雅或高效，但我是从初学者的角度（我是其中之一）在可读性和基本功能方面写的。

从右边开始，这将每隔一个数字加倍。

使用这个脚本：doubleEveryOther [1,3,6,9,12,15,18]生产[1,6,6,18,12,30,18]和 doubleEveryOther [1,3,6,9,12,15] 生产[2,3,12,9,24,15]

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther (x:[]) = [x]
doubleEveryOther (x:y:zs)
  |  (length (x:y:zs)) `mod` 2    /= 0    =    x : y*2 : doubleEveryOther zs
  |  otherwise                            =    x*2 : y : doubleEveryOther zs

Answer 5

一个直接的实现是：

doubleOddElements :: [Int] -> [Int]
doubleOddElements [] = []
doubleOddElements [x] = [2 * x]
doubleOddElements (x:y:xs) = (2*x):y:(doubleOddElements xs)

Answer 6

这是我的两个解决方案，请注意，我是 Haskell 的初学者。

第一个使用列表函数，head，tail和lenght：

doubleSecondFromEnd :: [Integer] -> [Integer]
doubleSecondFromEnd [] = []  -- Do nothing on empty list
doubleSecondFromEnd n
  | length n `mod` 2 == 0 = head n * 2 : doubleSecondFromEnd (tail n)
  | otherwise      = head n : doubleSecondFromEnd (tail n)

第二个，类似但不同的方法只使用长度函数：

doubleSecondFromEnd2 :: [Integer] -> [Integer]
doubleSecondFromEnd2 [] = []  -- Do nothing on empty list
doubleSecondFromEnd2 (x:y)
  | length y `mod` 2 /= 0 = x * 2 : doubleSecondFromEnd2 y
  | otherwise      = x : doubleSecondFromEnd2 y

Answer 7

尝试将问题概括一下：由于我们希望从末尾开始将每个第二个元素加倍，因此我们无法提前知道它是从一开始就是奇数还是偶数。所以最简单的方法是构建两者，计算整体大小是偶数还是奇数，然后再决定。

让我们定义一个Applicative数据结构来捕获：

• 有两种值的变体，
• 保持长度的奇偶性（奇/偶），和
• 当两个这样的值组合时，交替两者，

如下：

import Control.Applicative
import Data.Monoid
import qualified Data.Traversable as T

data Switching m = Switching !Bool m m
  deriving (Eq, Ord, Show)

instance Functor Switching where
    fmap f (Switching b x y) = Switching b (f x) (f y)

instance Applicative Switching where
    pure x = Switching False x x
    (Switching False f g) <*> (Switching b2 x y) = Switching b2 (f x) (g y)
    (Switching True  f g) <*> (Switching b2 x y) = Switching (not b2) (f y) (g x)

所以遍历一个列表会产生两个列表，如下所示：

x1 y2 x3 y4 ...
y1 x2 y3 x4 ...

两个曲折的副本。现在我们可以计算

double2 :: (Num m) => m -> Switching m
double2 x = Switching True (2 * x) x

double2ndRight :: (Num m, T.Traversable f) => f m -> f m
double2ndRight k = case T.traverse double2 k of
                    Switching True _ y -> y
                    Switching False x _ -> x

Answer 8

我的第一个想法是：

doubleOdd (x:xs) = (2*x):(doubleEven xs)
doubleOdd [] = []
doubleEven (x:xs) = x:(doubleOdd xs)
doubleEven [] = []

DiegoNolan 的解决方案更优雅，因为函数和序列长度更容易改变，但我花了一点时间去摸索。

添加从右侧操作的要求使其变得更加复杂。foldr是从右边做某事的一个很好的起点，所以让我试试：

doubleOddFromRight = third . foldr builder (id,double,[])
    where third (_,_,x) = x
          builder x (fx,fy,xs) = (fy, fx, fx x : xs)
          double x = 2 * x

这将交换两个函数fx和fy每个条目。要找到任何条目的值，都需要遍历列表的末尾，找出长度是奇数还是偶数。

Answer 9

我们也可以这样做：

doubleEveryOther = reverse . zipWith (*) value . reverse
    where
    value = 1 : 2 : value

Answer 10

我只是在学习Haskell，所以请找到以下初学者解决方案。我尝试使用有限的酷功能，如zipWith, cycle, 或reverse

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther s@(x:xs)
  | (length s) `mod` 2 == 0 = (x * 2) : (doubleEveryOther xs)
  | otherwise =  x : (doubleEveryOther xs)

需要注意的关键是，当从右侧将每个元素加倍时，您可以将加倍分为两种情况：

1. 如果列表的长度是偶数，您最终会将列表的第一个元素加倍。
2. 如果列表是奇数长度，则不会将列表的第一个元素加倍。

我在CS194的家庭作业中回答了这个问题

Answer 11

为了简单起见，这个怎么样？

doubleEveryOtherRev :: [Integer] -> [Integer]

doubleEveryOtherRev l = doubleRev (reverse l) []
  where
    doubleRev [] a = a
    doubleRev (x:[]) a = (x:a)
    doubleRev (x:y:zs) a = doubleRev zs (2*y:x:a)

---

如果您遵循该课程的建议，您将不得不提供一个反转的数字列表，因为当它再次反转时，它将使所有其他元素加倍。我认为这与使用两次反向函数不同，另一个是在两者之间每隔一个数字加倍，因为您不需要在第二次知道他们列表的全部范围。换句话说，它解决了该课程的问题，但如果我错了，请有人纠正我。

Answer 12

这是我对这个CIS 194家庭作业的回答。它仅使用第 1 课 + 中介绍的内容来实现reverse。

doubleEveryOtherLeftToRight :: [Integer] -> [Integer]
doubleEveryOtherLeftToRight []       = []
doubleEveryOtherLeftToRight (x:[])   = [x]
doubleEveryOtherLeftToRight (x:y:zs) = x:y*2:(doubleEveryOtherLeftToRight zs)

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse (doubleEveryOtherLeftToRight (reverse xs))

Answer 13

有些答案似乎不涉及列表的奇数/偶数长度。

doubleEveryOtherEvenList = zipWith ($) (cycle [(*2),id])

doubleEveryOther :: [Int] -> [Int]
doubleEveryOther n
    | length n `mod` 2 == 0 = doubleEveryOtherEvenList n
    | otherwise = (head n) : doubleEveryOtherEvenList (tail n)

Answer 14

在 haskell 中学习 edx 课程，这是我的菜鸟解决方案。

doubleSecondR :: [Integer] -> [Integer]

doubleSecondR xs = reverse(zipWith (*) (reverse xs) ys)

where ys = repeat' [1,2]

repeat' :: [a] -> [a]

repeat' xs = xs ++ repeat' xs

Answer 15

我猜 OP 在研究 Haskell CIS194 Course的作业 1 作业的答案时提出了这个问题。在课程的那个阶段向学生传授的 Haskell 很少，因此虽然上述答案是正确的，但它们超出了学习学生的理解范围，因为诸如 lambda、函数组合 (.) 甚至库例程之类的元素像长度和反向还没有介绍。这是一个与课程教学阶段相匹配的答案：

doubleEveryOtherEven :: [Integer] -> [Integer]
doubleEveryOtherEven []         = []
doubleEveryOtherEven (x:y:xs)   = x*2 : y : doubleEveryOtherEven xs

doubleEveryOtherOdd :: [Integer] -> [Integer]
doubleEveryOtherOdd (x:[])      = [x] 
doubleEveryOtherOdd (x:y:xs)    = x : y*2 : doubleEveryOtherOdd xs

integerListLen :: [Integer] -> Integer
integerListLen []       = 0 
integerListLen (x:xs)   = 1 + integerListLen xs

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs
    | integerListLen xs `mod` 2 == 0    = doubleEveryOtherEven xs   -- also handles empty list case
    | otherwise                         = doubleEveryOtherOdd xs

该计算需要预先知道列表是否具有偶数或奇数个元素，以确定每对数字中的哪个数字应加倍。但是，基本的 Haskell 模式匹配只允许从左到右匹配列表元素（例如：x:xs），这意味着在到达末尾之前您无法确定是奇数还是偶数列表，但到那时为时已晚，因为您需要在遍历列表以到达末尾时对每一对左侧元素进行计算。

解决方案是将加倍逻辑拆分为两个函数 - 一个处理偶数长度列表，另一个处理奇数长度列表。需要第三个函数来确定为给定列表调用这两个函数中的哪一个，这反过来又需要一个可以计算列表长度的附加函数，以便我们可以确定列表是否具有奇数或偶数元素（再次，因为在课程的这个阶段还没有介绍长度库函数）。

这个解决方案也与第 1 周课程中的建议保持一致，其中指出：“通过组合许多简单的函数来构建更复杂的函数是一种很好的 Haskell 风格。 ”

Answer 16

我也从CIS 194课程中来回答这个问题。

我做了这两种方式。首先，我认为问题的重点应该仅取决于列出的 3 个可能来源中的任何一个中提到的功能或编程方式。课程讲座 1，Real World Haskell ch。1,2和向您学习 Haskell ch。2 .

那么好吧：

• 递归，条件
• reversemax, , min, odd,等基本函数even
• 列出函数，例如head, tail, ...

不好：

• foldr, foldl,map
• 高阶函数
• 除了这些之外的任何东西

第一个解决方案，仅使用带有计数器的递归：

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = loopDoubles xs 1

loopDoubles :: [Integer] -> Integer -> [Integer]
loopDoubles [] _ =  []
loopDoubles xs n =  loopDoubles (init xs) (n + 1) ++ [doubleEven (last xs) n]

doubleEven :: Integer -> Integer -> Integer
doubleEven x n = if even n then x * 2 else x

此方法使用递归，但避免在递归的每一级计算长度。

第二种打破我上述规则的方法：

doubleEveryOther' :: [Integer] -> [Integer]
doubleEveryOther' xs =  map (\x -> if even (fst x) then (snd x) * 2 else snd x) $ zip (reverse [1..n]) xs
                        where n = length(xs)

第二个通过建立一组反向索引然后映射这些索引来工作。这确实计算了长度，但只计算了一次。

例如[1,1,1,1] -> [(4,1),(3,1),(2,1),(1,1)]

这两个都遵循将右边的所有其他元素加倍的要求。

> doubleEveryOther [1,2,3,4]
[2,2,6,4]
> doubleEveryOther [1,2,3]
[1,4,3]
> doubleEveryOther' [1,2,3,4]
[2,2,6,4]
> doubleEveryOther' [1,2,3]
[1,4,3]