Сканирование, которое разделяет аккумулятор и дает значение
Обновлено: функция, которую я просил, была mapAccumL
Проблема: разделить список целых чисел так, чтобы суммы подсписков были ограничены (10).
Вот как я бы решил это на Python, используя сканирование для выполнения условной логики:
l = random.choices(range(5), k=30)
[2, 3, 3, 1, 4, 0, 3, 2, 0, 3, 3, 1, 2, 0, 2, 1, 2, 4, 4, 3, 1, 4, 2, 0, 3, 1, 4, 1, 0, 2]
scan_result = *itertools.accumulate(l, lambda acc, x: x if acc + x >= 10 else acc + x),
(2, 5, 8, 9, 4, 4, 7, 9, 9, 3, 6, 7, 9, 9, 2, 3, 5, 9, 4, 7, 8, 4, 6, 6, 9, 1, 5, 6, 6, 8)
adjacent_map = lambda fn, l: itertools.starmap(fn, zip(l, l[1:]))
mask = (0, *adjacent_map(lambda a, b: int(a > b), scan_result))
(0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0)
С помощью маски вы можете разрезать исходный список на желаемый список списков:
[[2,3,3,1],[4,0,3,2,0],[3,3,1,2,0],[2,1,2,4],[4,3,1],[4,2,0,3],[1,4,1,0,2]]
Вы можете сделать это за один раз в scan, вернув маску. Но тогда ваша лямбда становится неловкой lambda acc, x: (x, 1, x) if acc[0] + x >= 10 else (acc[0] + x, 0, x).
Это не очень удовлетворительно. У него плохое разделение задач. acc[0] нужен только для логики сканирования и не нужен после него. После нужен только acc[1:]. Мне нужен алгоритм сканирования, который разделяет то, что вы возвращаете: result[0] становится следующим аккумулятором, result[1:] полученным результатом сканирования.
Была ли эта проблема решена раньше? Есть ли какой-либо предшествующий уровень техники? Люди делают это в Haskell? Есть ли в j или apl функции/операторы, которые это делают?
В стороне: кажется, вам нужно написать свою собственную библиотеку, чтобы получить хотя бы наполовину приличные решения. Я думаю, что моя проблема в том, что я программирую на C++, но не пишу свои собственные итераторы/диапазоны.
что значит «но не пишите свои собственные итераторы/диапазоны». означает?
Я прошу идеоматического Haskell, решения. Python легко писать и читать. Если бы я написал решение на Haskell, оно было бы изоморфно Python.
Хорошо, но почему тогда j и apl ? И почему вы говорите, что программируете на C++?
Я думал, у вас есть алгоритм для этого???
Тогда укажите это в вопросе. В настоящее время похоже, что вы использовали неправильные теги.
Кроме того, зачем давать ссылку на Jello cut?
@Адам, это классификация всех разновидностей этих алгоритмов. Большинство языков не поддерживают ни один из них. APL и J могли бы сделать несколько
Ответы 3
Мы можем написать собственное решение с помощью:
makeBins :: Int -> [Int] -> [[Int]]
makeBins t0 = go t0
where go t xa@(x:xs)
| x > t = [] : go t0 xa
| otherwise = let ~(y:ys) = go (t-x) xs in (x:y) : ys
go _ [] = [[]]
это дает нам образец данных:
ghci> makeBins 10 [2, 3, 3, 1, 4, 0, 3, 2, 0, 3, 3, 1, 2, 0, 2, 1, 2, 4, 4, 3, 1, 4, 2, 0, 3, 1, 4, 1, 0, 2]
[[2,3,3,1],[4,0,3,2,0],[3,3,1,2,0],[2,1,2,4],[4,3,1],[4,2,0,3,1],[4,1,0,2]]
что, таким образом, создает ячейки с 9, 9, 9, 9, 8, 10 и 7 в качестве промежуточных итогов.
Из примера ОП кажется, что желаемый результат имеет суммы 9, 9, 9, 9, 8, 9 и 8.
Нет, это похоже на правильный ответ. Сократить список так, чтобы суммы не превышали определенную границу. Это действительно распространенная проблема
Итак, вы говорите, что в Haskell идиоматично использовать для этого рекурсию. Если бы они сделали это с помощью итерации, сделали бы они это уродливым способом??
Почему у вас сложилось впечатление, что в Haskell существует итерация? Все, что в Haskell даже выглядит как итерация, на самом деле является рекурсией.
@LouisWasserman, извините, под итерацией я имел в виду инкапсуляцию рекурсии в fold и scan
Я думаю, что один идиоматический способ сделать это в Haskell без явной рекурсии — использовать его ленивость: мы создадим полный список сумм, но заглянем в него достаточно глубоко, чтобы увидеть что-то большее, чем 10. Вот так:
makeBins :: Int -> [Int] -> [[Int]]
makeBins n = unfoldr \case
[] -> Nothing
ns -> Just (splitAt (length (takeWhile (<n) (scanl1 (+) ns))) ns)
В качестве бонуса это позволяет более изящно обрабатывать списки с отрицательными числами, чем ваше решение на Python; однако он немного менее ленив и удобен для GC, чем явное рекурсивное решение в другом ответе. Это можно исправить, если необходим такой уровень оптимизации, с помощью функции, которая, вероятно, должна быть где-то в библиотеках и объединяет splitAt и length:
splitAtLength :: [a] -> [b] -> ([b], [b])
splitAtLength (_:as) (b:bs) = let ~(l, r) = splitAtLength as bs in (b:l, r)
splitAtLength [] bs = ([], bs)
С splitAtLength в руке второе предложение makeBins станет
ns -> Just (splitAtLength (takeWhile (<n) (scanl1 (+) ns)) ns)
и у вас будет полная лень/дружественность к GC.
https://haskell.godbolt.org/z/ExoKqh3xG
С помощью mapAccumL и комбинатора starling 1 2, который представляет собой <*>/ap для монады чтения в Haskell.
splitByMask :: [Bool] -> [Int] -> [[Int]]
fn :: Int -> Int -> (Int, Bool)
fn = \acc x -> if acc + x >= 10 then (x, True) else (acc + x, False)
makeBins :: (a -> Int -> (a, Bool)) -> [Int] -> [[Int]]
makeBins fn = ((flip splitByMask) <*> (snd . mapAccumL fn 0))
Программирование с комбинаторами на Haskell смотрите здесь youtu.be/umb5vTP_g7c?t=1518
Ваш Split_scanl почти равен MapAccumL. Это то же самое, за исключением того, что mapAccumL возвращает не только список, но и конечное состояние.
Что такое splitByMask?
@DavidFletcher Спасибо, это то, о чем я просил.
@DanielWagner вставьте ссылку. Это написал ChatGPT. Это было в ссылке на Godbolt.
@TomHuntington Ответы должны быть самостоятельными. Ссылка на дополнительную информацию — это нормально, но ссылка на сам ответ — нет. Также будьте осторожны: ответы, написанные в формате gpt, не допускаются.
Это похоже на Питон? Почему это отмечено тегами Haskell, j и apl?