haskell 我怎么能和一个列表的列表时,长度小于3长的无限列表?

hmae6n7t  于 2022-11-14  发布在  其他
关注(0)|答案(2)|浏览(121)

我的代码可以工作,但不能处理无尽的列表。我如何才能让它工作?

sumsOf :: Num a => [[a]] -> [a]
sumsOf a = map sum [ x | x <- a , length x < 3]

示例:

sumsOf [[],[1,2,4],[],[6]] == [0,0,6]
sumsOf [[1],[8],[6],[],[9,9]] == [1,8,6,0,18]
sumsOf [[1,2,9,10],[7,8,9],[6,9,4,2,0],[9,9,9]] == []
sumsOf [[1..],[7..],[6..],[9..],[10..],[100..]] == []
sumsOf [[1,2], [1..], [], [4]] == [3,0,4]
c3frrgcw

c3frrgcw1#

length是列表函数之一,作为经验法则,您应该永远不要使用它,除非您确切地知道它为什么可以使用。(另一个是head!!。)这不仅仅是因为它不能处理无限列表,也是因为它做了一个通常完全不必要的(n)遍历整个列表。即使你以后无论如何都要遍历它,做两次也会带来很大的性能差异。
在这种情况下,想想你真正需要的是什么:一个sum,它避免进入一个长的或无限的列表,而是在两个元素之后放弃。这实际上可以用一种愚蠢的穷举方法来实现:

sumIfLenLt3 :: Num a => [a] -> Maybe a
sumIfLenLt3 [] = Just 0
sumIfLenLt3 [x] = Just x
sumIfLenLt3 [x,y] = Just $ x+y
sumIfLenLt3 _ = Nothing

要使它对任何max-length都通用,可以使用递归:

sumIfLenLe :: Num a => Int -> [a] -> Maybe a
sumIfLenLe _ [] = Just 0
sumIfLenLe 0 _ = Nothing
sumIfLenLe n (h:t) = h + sumIfLenLe (n-1) t

...但这并不是一个很好的实现,原因有二:它会因为负参数而崩溃,而且它不是尾递归的。

sumIfLenLe :: Num a => Int -> [a] -> Maybe a
sumIfLenLe n l
  | n<0        = Nothing
  | otherwise  = go n l 0
 where go n [] acc  = Just acc
       go 0 _ _ = Nothing
       go n (h:t) acc = go (n-1) t (h+acc)

更优雅的做法是使用一个标准函数来获取元素的最大可用计数,并查看是否还有剩余:

sumIfLenLe :: Num a => Int -> [a] -> Maybe a
sumIfLenLe n l
  | null remains  = Just $ sum relevant
  | otherwise     = Nothing
 where (relevant, remains) = splitAt n l

...或一些等效形式,

sumIfLenLe n l = case splitAt n l of
   (relevant, []) -> Just $ sum relevant
   _              -> Nothing

sumIfLenLe n l
 | (relevant, []) <- splitAt n l
              = Just $ sum relevant
 | otherwise  = Nothing

然后,您可以将其Map到整个给定的列表,并收集所有成功的结果。

import Data.Maybe (catMaybes)

sumsOf :: Num a => [[a]] -> [a]
sumsOf = catMaybes . map (sumIfLe 2)
fjaof16o

fjaof16o2#

简单懒惰的解决方案:

您只关心长度是否小于3,因此如果您将输入列表截断为3个元素,结果不会更改:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> sumsOf a = map sum [ x | x <- a , length (take 3 x) < 3]
 λ> 
 λ> sumsOf [[],[1,2,4],[],[6]]
 [0,0,6]
 λ> sumsOf [[1],[8],[6],[],[9,9]]
 [1,8,6,0,18]
 λ> sumsOf [[1,2,9,10],[7,8,9],[6,9,4,2,0],[9,9,9]]
 []
 λ> sumsOf [[1..],[7..],[6..],[9..],[10..],[100..]]
 []
 λ> sumsOf [[1,2], [1..], [], [4]]
 [3,0,4]
 λ>

因此,这很容易解决无限列表的问题。
以稍微更惯用的方式:

sumsOf :: Num a => [[a]] -> [a]
sumsOf xss = map sum [ xs | xs <- xss , length (take 3 xs) < 3]

唯一的缺点是库函数take必须复制列表节点。
在n.1.8e9的评论中提到了一个想法--我的共享在哪里:通过编写一些boundedLength函数,最多返回k,可以得到更有效的结果,例如:

boundedLength :: Int -> [a] -> Int
boundedLength k xs = go 0 xs
  where
    go depth   []    =  depth
    go depth (x:xs)  =  if (depth < k)  then  go (depth + 1) xs
                                        else  k

在这种情况下,我们的sumsOf函数的结果为:

sumsOf :: Num a => [[a]] -> [a]
sumsOf xss = map sum [ xs | xs <- xss , boundedLength 3 xs < 3]

相关问题