Свертки в haskell

то есть accumulator должен быть списком

Парой (число, список). Когда число обнулится, можно начать добавлять элементы в список.

mydrop n xs = foldl (\x acc -> if (snd acc) <= n then ([], (snd acc) + 1) else (x : (fst acc), (snd acc))) ([], 0) xs

Выдает ошибку

<interactive>:67:81: error:
    • Occurs check: cannot construct the infinite type: t1 ~ ([t1], b)
      Expected type: [t1]
        Actual type: [([t1], b)]
    • In the expression: x : (fst acc)
      In the expression: (x : (fst acc), (snd acc))
      In the expression:
        if (snd acc) <= n then
            ([], (snd acc) + 1)
        else
            (x : (fst acc), (snd acc))
    • Relevant bindings include
        acc :: ([([t1], b)], b) (bound at <interactive>:67:25)
        x :: ([t1], b) (bound at <interactive>:67:23)
        xs :: t ([([t1], b)], b) (bound at <interactive>:67:10)
        n :: b (bound at <interactive>:67:8)
        mydrop :: b -> t ([([t1], b)], b) -> ([t1], b)
          (bound at <interactive>:67:1)

Почему такой тип acc :: ([([t1], b)], b)?

В ghci код 0 : fst ([1,2,3],0) работает нормально

то есть accumulator должен быть списком

Тебе нужно ещё как-то отслеживать, сколько элементов уже дропнуто, поэтому в качестве аккумулятора должна быть пара <число дропнутых элементов, список>:

import Prelude hiding (drop)

drop :: Int -> [a] -> [a]
drop n = reverse . snd . foldl f (0, [])
  where f (i, acc) x | i >= n    = (i, x : acc)
                     | otherwise = (i + 1, acc)

Замени foldl на foldr только.

по логике в ветке else я возвражаю пару первый элемент которого список с добавленным элементом а второй элемент пары это счетчик. Список строю только для первого элемента а тип асс представлен как пара первый элемент список пар...

Выдает ошибку

Ты перепутал порядок аргументов в функции, которую принимает foldl. Должно быть <аккумулятор>, <элемент списка>, а у тебя <элемент списка>, <аккумулятор>.

Тогда нужно переворачивать исходный список.

Тогда нужно переворачивать исходный список.

Тогда на foldl'. Иначе у тебя thunk вырастет.

P.S. Ну или вообще заменить список на Seq в аккумуляторе. Должно быть быстрее чем reverse.

Спасибо всем за помощь, разобрался.

Не пиши однострочники. where — твой друг.

if snd fst fst snd

Про паттерн-матчинг не слышал?

drop' :: Int -> [a] -> [a]
drop' n = fst . foldr dropElem ([], n) where
    dropElem y (xs, 0) = (y:xs, 0)
    dropElem _ (_, n) = ([], n - 1)

Можно красиво в аппликативном стиле, с одним проходом. Тут везде частичное применение функций:

drop' :: Int -> [a] -> [a]
drop' n = foldr (\(i, x) -> if i < n then id else (x :)) [] . zip [0 ..]

drop с начала списка дропает, а не с конца, вообще-то.

Тогда на foldl'

Это уже будет не drop. Попробуй найди drop 2 [undefined, undefined, 1].

С foldl - тоже не drop. Как раз из-за накопления thunk. Плюс drop не проходит весь список. Это если уж мы говорим о точном совпадение семантики.

Я показал, как делать с foldr. Хотя в вычислении разница незаметна, но надо отметить, что drop, в отличие от foldr, проходит только первые n элементов списка.

Спасибо за совет, я пока не проникся духом haskell, поэтому пишу так топорно))

А можешь описать подробнее как работает? При вызове функции 1 шаг zip преобразует в лист пар [(index, value)]. Лямбда передаваемая foldr частично пременена(к текущему элемену) и возвращает функцию либо id либо (x :) и тут для меня начинается магия... В какой момент происход вызов функции возвращаемой лямбдой?

В какой момент происход вызов функции возвращаемой лямбдой?

В таких терминах семантику свертки понять трудно. Я для себя использую другое объяснение: Проще всего запоминается foldr как право-ассоциативная свертка, для передаваемой функции в foldr исходим из того, что ее правый (второй) аргумент — накопленный результат res, а левый (первый) — текущий элемент списка. Результат вызова функции выдает накопленный результат с учетом данного элемента списка. Что примечательно, foldl (только вместо него нужно использовать не-ленивый foldl') — это лево-ассоциативная свертка, и поэтому результат и элемент списка в ее функции меняются местами (результат слева, то есть первый аргумент функции).

Поэтому мысленно мы можем дополнить аргументы функции:

\(i, x) res -> (if i < n then id else (x :)) res

Применим частичные функции к res:

\(i, x) res -> if i < n then res else (x : res)

спасибо