时间戳

首页 > 解决方案 > 获取满足条件的最短列表前缀

haskell - 获取满足条件的最短列表前缀

问题描述

假设我有一个列表，并且想要获取列表的最短前缀以满足条件。例如，假设我想获得一个整数列表的前缀，其总和至少为给定数字。一种方法：

module ListPrefix where

import Data.Maybe

lpref :: Int -> [Int] -> Maybe [Int]
lpref w xs =
  let f l r s
        | s >= w    = Just (reverse l)
        | null r    = Nothing
        | otherwise = f (head r : l) (tail r) (s + head r)
  in f [] xs 0

main = do
  print $ lpref 48 [1..100]

有没有办法在不使用手动递归的情况下编写这个？

编辑：

根据Willem的建议，一个更好的版本：

lpref2 :: Int -> [Int] -> Maybe [Int]
lpref2 w xs =
  let f t@(ys, s) e = if s >= w then t else (e : ys, s + e)
      (fs, s) = foldl f ([], 0) xs
  in if s >= w then Just (reverse fs) else Nothing

让我知道这是否可以改进！

标签： haskell

解决方案

这是一个简单、简洁的方法，虽然可能不是最有效的：

import Data.List (find, inits)

lpref :: Int -> [Int] -> Maybe [Int]
lpref w = find (\xs -> sum xs >= w) . inits

至于您的尝试，首先要注意的是，在常规列表中，foldl总是错误的。您应该始终使用foldl'或foldr代替。此外，测试null然后使用headandtail作为反模式。

为了最大限度地提高效率，我会采取以下措施：

lpref :: Int -> [Int] -> Maybe [Int]
lpref w xs
  | 0 >= w = Just []
  | otherwise = foldr go mempty xs 0 id
  where
    go :: Int -> (Int -> ([Int] -> [Int]) -> Maybe [Int]) -> Int -> ([Int] -> [Int]) -> Maybe [Int]
    go x acc s f
      | s' >= w = Just $ f [x]
      | otherwise = acc s' (f . (x:))
      where s' = x + s

这也是最大的懒惰。lpref 6 (1:2:3:undefined)返回Just [1,2,3]。

推荐阅读