理解函数中的Haskell递归

Question

我一直在为Haskell使用一些资源:了解一下Haskell和wikibook.但是,我很难找到一个解释,帮助我更多地理解递归.我附上了一本代码来自'Learn you a Haskell'一书,我对此有所了解.

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs

我理解上面的所有代码,直到最后一行'maxTail = maximum'xs'.我不明白的是,如何通过调用最大值来评估代码以返回最大值.或者它如何知道最大'是列表中的最高元素.

另一个例子:

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]

了解所有内容,直到在列表的尾部调用reverse'.换句话说,它如何知道反向'意味着反转尾部元素.

我真的很感激解释,并且如果它很简单就道歉,我是这种语言的新手.

Answer 1

逐行排列,所以你希望更好地理解它:

1| maximum' :: (Ord a) => [a] -> a  
2| maximum' [] = error "maximum of empty list"  
3| maximum' [x] = x  
4| maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs

在第1行:你说你得到一个列表并返回该类型的一个元素.此外,该列表中的元素必须是可以包含的,因此您可以将它们放入订单中.

在第2行:你有一个边缘情况,你说如果你得到一个空列表作为输入,那个空列表中不能有"最高值",所以你结束该函数有一个错误.

在第3行:你有另一个边缘情况,你说如果你得到一个包含1个元素的列表,那个元素必须是最高元素,所以你返回它.

在第4行:您使用模式匹配来匹配第一个元素(x)和列表的其余部分(xs).然后检查是否x大于maxTail,maxTail函数调用的结果maximum'与列表的其余部分一致xs.

如果那x比maxTail你那么大,你就会回来x,否则maxTail就会大于x你的回归maxTail.

我认为有一些数字的例子也应该有帮助:

输入:

[2, 5, 4, 13]

呼叫:

maximum' [2, 5, 4, 13]

怎么了:

maximum' (x  :  xs)
          ?     ?
maximum' (2:[5, 4, 13]) 
           ?
           ?                               result 13
     x > maxTail = x                         ?
     2 > maximum' [5, 4, 13] = x  //2 > 13 = 13 ? ?????
         ?                                            ?
         ?  maximum' (x :  xs)                        ?
                      ?    ?                          ?
            maximum' (5:[4, 13])                      ?
                       ?                              ?
                       ?                              ?
                 x > maxTail = x                      ?
                 5 > maximum' [4, 13] = x  //5 > 13 = 13 ? ??????
                     ?                                          ?
                     ?  maximum' (x: xs)                        ?
                                  ?  ?                          ?
                        maximum' (4:[13])                       ?
                                   ?                            ?
                                   ?                            ?
                              x > maxTail = x                   ?
                              4 > maximum' [13] = x  //4 > 13 = 13  ?
                                  ?                                 ?
                                  ? maximum' [x] = x                ?
                                    maximum' [13] = 13 ? ????????????

在你的第二个例子中,它几乎是一样的:

1| reverse' :: [a] -> [a]  
2| reverse' [] = []  
3| reverse' (x:xs) = reverse' xs ++ [x]

在第1行:你说你得到一个列表并返回一个列表.

在第2行:你有一个边缘情况,你说如果你得到一个空列表,反向列表也只是空的.

在第3行:你再次使用模式匹配来匹配x列表的第一个元素()和它的tail(xs).

现在你只需++要将两个列表附加在一起,这是列表中带有反转尾部的第一个元素.

我希望再举一个例子,它会更清楚一些:

输入:

[1, 2, 3]

呼叫:

reverse' [1, 2, 3]

怎么了:

reverse' (x : xs)
          ?   ?
reverse' (1:[2, 3])
           ?                               result [3, 2, 1]
           ?                                       ?
   (reverse' [2, 3]) ++ [1]  //[3, 2] ++ [1] = [3, 2, 1] ? ?????
    ?                                                          ?
    ? reverse' (x: xs)                                         ?
                ?  ?                                           ?
      reverse' (2:[3])                                         ?
                 ?                                             ?
                 ?                                             ?
         (reverse' [3]) ++ [2]  //[3] ++ [2] = [3, 2] ? ???? ? ?
          ?                                                ?
          ? reverse' (x:xs)                                ?
                      ? ?                                  ?
            reverse' (3:[])                                ?
                       ?                                   ?
                       ?                                   ?
               (reverse' []) ++ [3]  //[] ++ [3] = [3] ? ? ?
                ?                                      ?           
                ? reverse' [] = [] ? ???????????????????