理解奇数和偶数索引列表背后的Haskell逻辑

628mspwn  于 12个月前  发布在  其他
关注(0)|答案(2)|浏览(191)

我在haskell中有一个问题,要求一个函数将一个列表分成两个不同的列表,这样偶数索引填充一个列表,奇数索引填充另一个列表。示例:

func :: [Int] -> ([Int], [Int])

字符串
然后,如果我们输入[44,8,11,23],我们期望收到[44,11]和[8,23].在互联网上看,我发现了一个伟大的和geniaus解决方案,但不能理解背后的逻辑:

func :: [Int] -> ([Int], [Int])
func [] = ([], [])
func [x] = ([x], [])
func (x:y:xs) = (x:odds, y:evens)
    where
    (odds, evens) = func xs


我知道haskell中有“奇”和“偶”函数,但“奇s”和“偶s"是什么意思?这些值是如何正确地进入某个列表的?我为此感到疑惑。
我正在寻找几个论坛和教程,试图理解这段代码的逻辑,但我在零水平,直到现在。

9rygscc1

9rygscc11#

我知道haskell中有“奇”和“偶”函数,但是“奇s”和“偶s"是什么意思呢?
oddsevens只是变量名。它们与oddeven函数没有直接关系。它们是复数(以s结尾),因为这是Haskell对列表的命名约定。
让我们从func [44, 8, 11, 23]开始,逐步完成示例输入。
由于这是一个递归函数,所以会有多个调用func,它们都有自己的局部变量。为了避免混淆,我将为每个调用的局部变量添加数字,例如x1x2,而不仅仅是x
首先,func [44, 8, 11, 23]匹配func的第三个子句func (x : y : xs)

let
  x1 = 44
  y1 = 8
  xs1 = [11, 23]
  (odds1, evens1) = func xs1
in (x1 : odds1, y1 : evens1)

字符串
这可以简化一点。

let
  (odds1, evens1) = func [11, 23]
in (44 : odds1, 8 : evens1)


现在我们需要知道func [11, 23]的值。这也匹配第三个子句。

let
  (odds1, evens1) = let
    x2 = 11
    y2 = 23
    xs2 = []
    (odds2, evens2) = func xs2
    in (x2 : odds2, y2 : evens2)
in (44 : odds1, 8 : evens1)


再一次,我们可以简化。

let
  (odds1, evens1) = let
    (odds2, evens2) = func []
    in (11 : odds2, 23 : evens2)
in (44 : odds1, 8 : evens1)


最后,func []匹配第一个子句func [] = ([], [])

let
  (odds1, evens1) = let
    (odds2, evens2) = ([], [])
    in (11 : odds2, 23 : evens2)
in (44 : odds1, 8 : evens1)


所以我们可以继续简化,直到我们得到一个解决方案。

let
  (odds1, evens1) = let
    odds2 = []
    evens2 = []
    in (11 : odds2, 23 : evens2)
in (44 : odds1, 8 : evens1)
let
  (odds1, evens1) = (11 : [], 23 : [])
in (44 : odds1, 8 : evens1)
let
  odds1 = 11 : []
  evens1 = 23 : []
in (44 : odds1, 8 : evens1)
(44 : 11 : [], 8 : 23 : [])
([44, 11], [8, 23])
fkvaft9z

fkvaft9z2#

一件一件来:

func (x:y:xs) = ...

字符串
当输入的长度>=2时,从xy开始,然后继续列表xs.

... = (x:odds, y:evens)


.结果是一对,其第一个分量是x : odds,第二个分量是y : evens。变量oddsevens定义为.

where
    (odds, evens) = func xs


.这些(列表)值是由递归调用func xs产生的。
让我们举个例子:

func [1,2,3,4] =
func (1:2:xs) =   -- with xs = [3,4]
(1:odds, 2:evens) 
where (odds, evens) = func xs = func [3,4]


为了完成计算,我们计算递归调用:

func [3,4] =
func (3:4:xs2) =  -- with xs2 = []
(3:odds2, 4:odds2)
where (odds2, evens2) = func xs2 = func []


再递归调用一次computing,但这是立即的:func [] = ([], [])
所以我们有

(odds2, evens2) = func [] = ([],[])
-- hence
odds2 = evens2 = []


发现了这一点后,我们从前面的方程中得到:

func [3,4] = (3:[], 4:[]) = ([3], [4])


所以我们有

(odds, even) = ([3], [4])
-- hence
odds = [3]
evens = [4]


所以我们从更古老的方程中得到:

func [1,2,3,4] = (1:odds, 2:evens) = (1:[3], 2:[4]) = ([1,3], [2,4])

相关问题