Реализация функции take в Haskell с использованием foldl

Question

Реализация функций Haskell take и drop с использованием foldl.

Любые предложения о том, как реализовать функции взятия и отбрасывания с использованием foldl ??

take x ls = foldl ???

drop x ls = foldl ???

Я пробовал это, но он показывает ошибки:

myFunc :: Int -> [a] -> [a]
myFunc n list = foldl func [] list
    where 
    func x y | (length y) > n = x : y 
             | otherwise      = y

Произведена ошибка:

*** Expression : foldl func [] list
*** Term : func
*** Type : a -> [a] -> [a]
*** Does not match : [a] -> [a] -> [a]
*** Because : unification would give infinite type

Answer 1

Хочу заметить, что вы никогда не указывали, что сгиб должен быть над предоставленным списком.Итак, один из подходов, который соответствует букве вашего вопроса, хотя, вероятно, не соответствует духу:

sillytake :: Int -> [a] -> [a]
sillytake n xs = foldl go (const []) [1..n] xs
  where go f _ (x:xs) = x : f xs
        go _ _ []     = []

sillydrop :: Int -> [a] -> [a]
sillydrop n xs = foldl go id [1..n] xs
  where go f _ (_:xs) = f xs
        go _ _ []     = []

Каждый из них использует левые сгибы, но над списком чисел [1..n]- сами числа игнорируются, а список просто используется по длине для создания пользовательской функции take n или drop n для заданного n.Затем эта функция применяется к исходному предоставленному списку xs.

Эти версии отлично работают с бесконечными списками:

> sillytake 5 $ sillydrop 5 $ [1..]
[6,7,8,9,10]

Answer 2

Не может быть сделано.

Сгиб влево обязательно расходится в бесконечных списках, а take n - нет. Это так, потому что левый сгиб хвостовой рекурсии, поэтому он должен просмотреть весь список ввода, прежде чем он сможет начать обработку.

При правильном сгибе это

ntake :: Int -> [a] -> [a]
ntake 0 _  = []
ntake n xs = foldr g z xs 0
    where
    g x r i | i>=n      = []
            | otherwise = x : r (i+1)
    z _ = []

ndrop :: Int -> [a] -> [a]
ndrop 0 xs = xs
ndrop n xs = foldr g z xs 0 xs
    where
    g x r i xs@(_:t) | i>=n      = xs
                     | otherwise = r (i+1) t
    z _ _ = []

ndrop реализует параморфизм красиво и верно, вплоть до порядка аргументов функции-редуктора g, предоставляя ему доступ как к текущему элементу x, так и к текущему узлу списка xs (такой, что xs == (x:t)), а также рекурсивный результат r. Редуктор катаморфизма имеет доступ только к x и r.

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

Что касается ошибки типа, чтобы исправить ее, просто переключите аргументы на func:

       func y x | ..... = .......

Аккумулятор в левом сгибе является аргументом first для функции-редуктора.

---

Если вы действительно хотите сделать это с левой складкой, и если вы действительно уверены, что списки конечны, два варианта:

ltake n xs = post $ foldl' g (0,id) xs
    where
    g (i,f) x | i < n = (i+1, f . (x:))
              | otherwise = (i,f)
    post (_,f) = f []

rltake n xs = foldl' g id xs r n
    where
    g acc x = acc . f x
    f x r i | i > 0 = x : r (i-1)
            | otherwise = []
    r _ = []

Первое считается слева направо вверх, потенциально останавливая сборку префикса в середине обхода полного списка, который он, тем не менее, переносит до конца, будучи левым сгибом.

Второй также полностью пересекает список, превращая его в правый сгиб, который , а затем снова начинает работать с обратным отсчетом слева и может фактически перестать работать, как только префикс собран.

Реализация drop таким образом неизбежно будет (?) Еще более громоздкой. Может быть хорошим упражнением.

Answer 3

Уилл Несс показал хороший способ реализации take с помощью foldr.Наименее отвратительный способ реализации drop с foldr заключается в следующем:

drop n0 xs0 = foldr go stop xs0 n0
  where
    stop _ = []
    go x r n
      | n <= 0 = x : r 0
      | otherwise = r (n - 1)

Возьмите потерю эффективности и перестройте весь список, если у вас нет выбора!Лучше вбить гвоздь с помощью отвертки, чем вбить винт молотком.

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

Складки просто не являются подходящими инструментами для реализации drop; параморфизм - правильный инструмент.

Answer 4

Вы не слишком далеко. Вот пара исправлений.

Во-первых, обратите внимание, что func передается сначала аккумулятору (т. Е. Список a, в вашем случае), а затем элементу списка (a). Итак, вам нужно поменять местами аргументы func.

Тогда, если мы хотим имитировать take, нам нужно добавить x, когда length y на меньше , чем n, не больше!

Итак, мы получаем

myFunc :: Int -> [a] -> [a]
myFunc n list = foldl func [] list
    where 
    func y x | (length y) < n = x : y 
             | otherwise      = y

Тест:

> myFunc 5 [1..10]
[5,4,3,2,1]

Как вы можете видеть, это переворачивает строку. Это потому, что мы добавляем x спереди (x:y), а не сзади (y++[x]). Или, в качестве альтернативы, можно использовать reverse (foldl ....), чтобы исправить порядок в конце.

Кроме того, так как foldl всегда сканирует весь список ввода, myFunc 3 [1..1000000000] займет много времени, и myFunc 3 [1..] не удастся завершить. Использование foldr было бы намного лучше.

drop более сложно сделать. Я не думаю, что вы можете легко сделать это без какой-либо постобработки, такой как myFunc n xs = fst (foldl ...) или заставить foldl возвращать функцию, которую вы немедленно вызываете (что также является разновидностью постобработки).