И снова Haskell. Эффективный Трибоначчи.

[Pulseofmalstrem]

Доброе время суток!
Столкнулся со следующей задачей: необходимо вывести список длиной n, состоящий из чисел Трибоначчи (как Фибоначчи только по три складываются), сделать это быстро и памяти много не занимать!
Сначала я решил задачу так:

Используется синтаксис Haskell

Trib :: (a, a, a) -> Int -> [Int]
Trib (a, b, c) n = map Tribonachi [1.. n]
     where Tribonachi 1 = a
                 Tribonachi 2 = b
                 Tribonachi 3 = c
                 Tribonachi n = Tribonachi (n - 1) + Tribonachi (n - 2) + Tribonachi (n - 3)
 

Но это было слишком медленно, что впрочем легко предсказуемо. Тогда я, вспомнив про идею использования аккумулятора, написал такой код:

Используется синтаксис Haskell

Trib :: (a, a, a) -> Int -> [Int]
Trib (a,b,c) n = Tribonachi [a, b, c] n
    where Tribonachi xs n = if length xs == n then xs
                                                                              else Tribonachi (xs ++ [last xs + last (init xs) + last (init(init xs))]) n
 

На этот раз сожрало слишком много памяти, тогда я попытался сэкономить память там, где у меня идет слияние двух список (а именно на втором ее аргументе), введя еще 3 аккумулятора (чтобы не нужно было создавать кучу разных список с init), но тогда снова вышел за рамки времени. Последняя надежда какая-нибудь лямбда-абстракция,но я точно ее не придумал пока. Прошу помощи. Где тут можно оптимизировать дальше?

[Xaositect]

В аккумуляторе не обязательно хранить весь список, достаточно трех последних членов.

[arseniiv]

Pulseofmalstrem в сообщении #1029762 писал(а):

last (init(init xs))

Код намекает, что его лучше переписать с pattern matching’ом. В самом деле, у вас и в оригинальном варианте, и в улучшении Xaositect в списке будет не менее трёх элементов — так зачем писать xs, когда можно (a:b:c:_) (или во втором случае просто [a,b,c])?

Плюс, надо было воспринимать список задом наперёд, т. к. init и last не так безобидны как tail и head.

[_Ivana]

Потоки текут, фьюзятся и мемоизируются при вынуждении.

Используется синтаксис Haskell

task n = take n t where
    t = 0:1:1:zipWith3 (\x y z -> x+y+z) t (tail t) (tail $ tail t)