理解递归函数列表中的列表 - haskell

Question

我正在编写一个函数来按元组或三元组排序给定列表.它应该按照列表中两个元素之间的数字来排序.

例如,如果给定列表是[1,2,3,6,7]它应该返回,[[1,2,3], [6,7]] 因为在1,2和2,3之间以及在6,7之间存在零数

这是我的代码:

import Data.List 

check :: [Int] -> [[Int]]
check listCopy@(x:xs) = 
    let sorted = sort (listCopy) 
        in if (length sorted > 1) 
              then if ((sorted !! 1 ) - (sorted !! 0)) == 1 || ((sorted !! 1 ) - (sorted !! 0)) == 0 
                      then [[x]  ++ check(xs) !! 0] 
                      else [[x]] ++ check(xs)
              else [[x]]
check [] = [[]]

if ((sorted !! 1 ) - (sorted !! 0)) == 1 || ((sorted !! 1 ) - (sorted !! 0)) == 0 正在检查列表的两个元素之间是否有0个数字

如果above语句为True,则[[x] ++ check(xs) !! 0]将该元素添加到列表中并再次调用该函数并获取它返回的第一个元素.示例:[1,2,3,6,7] -> [[1 ++ check [2,3,6,7]]] -> [[1,2 ++ check[3,6,7]]]依此类推......

但是当if ((sorted !! 1 ) - (sorted !! 0)) == 1 || ((sorted !! 1 ) - (sorted !! 0)) == 0False时,它应该else [[x]] ++ check(xs)将元素设置在列表中的列表内并再次调用函数并在列表中创建另一个新列表.示例:[[1,2 ++ check[3,6,7]]]- >是6-3 == 0或1(False)返回[[1,2,3]] + check[6,7]应该导致[[1,2,3],[6,7]]

check[1,2,3,6,7]然而,呼叫返回[[1,2,3]].我没有得到任何错误,但正如我所知,[[1,2]] ++ [[3,4]]应该导致[[1,2], [3,4]],这正是我正在做的事情else [[x]] ++ check(xs),不知怎的,我的功能在那里结束.我在哪里弄错了,或者它做了我遗失的事情？

Answer 1

这里的一个问题是你只附加了第一个子列表:

then [[x]  ++ check(xs) !! 0]

因此,您将进行一个递归调用,返回一个子列表列表,但是您"扔掉"所有列表但是第一个列表,然后连接第一个列表.其余的子列表将被忽略.

你可以解决这个问题:

then [[x]  ++ check(xs) !! 0] ++ safeTail check

我们在哪里实施safeTail:

safeTail :: [a] -> [a]
safeTail (x:xs) = xs
safeTail [] = []

或者像@melpomene说:

safeTail :: [a] -> [a]
safeTail = drop 1

稍后我们可以使用tail,但是使用上面的代码,很难看到.

但实施不是很"Haskellish".你的代码使用了很多(!!)s和lengths.由于(!!)在O(k)中运行,其中k是我们想要获取元素的索引,并且length在O(n)中以n列表的长度运行,这也将是非常低效的.

在进一步处理列表之前首先对列表进行排序是有意义的.接下来,我们只需要查找当前元素x,下一个元素n以及其余元素xs,所以:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:n:xs) = ...
go other = other

在这种情况下n <= x+1,我们知道两个数字之间的差异是零或一,所以在这种情况下,应该预先附加递归调用的头(第一个元素)x,所以我们可以这样写:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:n:xs) | n <= x+1 = (x:r) : rs
            | otherwise = ...
   where (r:rs) = go (n:xs)
go [x] = [[x]]
go [] = []

否则我们可以构建一个单例列表,然后是列表的其余部分:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:n:xs) | n <= x+1 = (x:r) : rs
            | otherwise = [x]:(r:rs)
    where (r:rs) = go (n:xs)
go [x] = [[x]]
go [] = []

我们知道go (n:xs)至少有一个元素,因为我们用一个元素递归地调用列表,并且在列表非空的所有情况下,我们返回一个非空列表.

通过使用as-pattern,我们可以使它更优雅:

go :: (Ord n, Num n) => [n] -> [[n]]
go (x:na@(n:xs)) | n <= x+1 = (x:r) : rs
                 | otherwise = [x]: ra
    where ra@(~(r:rs)) = go na
go [x] = [[x]]
go [] = []

我们可以概括上述内容,如@chepner所说,只需要Eq a,和Ord a:

go :: (Ord n, Enum n) => [n] -> [[n]]
go (x:na@(n:xs)) | succ x >= n = (x:r) : rs
                 | otherwise = [x]: ra
    where ra@(~(r:rs)) = go na
go [x] = [[x]]
go [] = []

所以,现在我们只需要表达check来讲go,有:

import Data.List(sort)

check :: (Ord n, Enum n) => [n] -> [[n]]
check = go . sort
    where go (x:na@(n:xs)) | succ x >= n = (x:r) : rs
                           | otherwise = [x]: ra
              where ra@(~(r:rs)) = go na
          go [x] = [[x]]
          go [] = []

或者我们可以让check函数对(Eq n, Enum n)类型进行操作:

import Data.List(sortBy)
import Data.Ord(comparing)

check :: (Ord n, Enum n) => [n] -> [[n]]
check = go . sortBy (comparing fromEnum)
    where go (x:na@(n:xs)) | succ x == n || x == n = (x:r) : rs
                           | otherwise = [x]: ra
              where ra@(~(r:rs)) = go na
          go [x] = [[x]]
          go [] = []