Получить префикс кратчайшего списка, удовлетворяющий условию

Question

Допустим, у меня есть список, и я хочу получить самый короткий префикс списка, удовлетворяющий условию. Например, скажем, я хочу получить префикс списка целых чисел, который суммируется до минимального заданного числа. Один из способов сделать это:

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]

Есть ли способ написать это без использования ручной рекурсии?

Изменить:

Немного лучше версия основана на предложении Виллема :

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

Сообщите мне, можно ли это улучшить!

Answer 1

Вот простой и лаконичный способ, хотя, вероятно, не самый эффективный:

import Data.List (find, inits)

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

Что касается вашей попытки, первое, что следует отметить, это то, что в обычных списках foldl всегда неверно. Вы всегда должны использовать вместо него foldl' или foldr. Кроме того, тестирование null, а затем использование head и tail в качестве анти-шаблона.

Вот что я бы сделал, чтобы максимизировать эффективность:

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].