Nano Hash - криптовалюты, майнинг, программирование

Как реализовать zip с помощью foldl (на нетерпеливом языке)

Один знакомый мне программист Clojure недавно заметил, что можно реализовать множество функций последовательности в терминах Clojure reduce (который является foldl' Haskell), но, к сожалению, нет способа реализовать (map list xs ys) (который является zip Haskell) всего лишь с reduce.

Я читал об универсальности складок, поэтому почти уверен, что это неправда: конечно zip возможно с foldr, и я был бы удивлен, если бы это было невозможно с foldl. В целях этого обсуждения мы игнорируем проблемы рвения foldl по сравнению с foldr: представьте, что у нас неограниченная память и мы работаем только с конечными последовательностями.

Итак, я взял код Haskell, чтобы реализовать zip с помощью foldr, и перевел его на Clojure, выполнив лучше всего скорректировать разницу между foldr и foldl:

(defn zip [xs ys]
  (letfn [(done [_] [])
          (step [z x]
            (fn [ys]
              (if (empty? ys)
                []
                (conj (z (rest ys)) [x (first ys)]))))]
    ((reduce step done xs) ys)))
user> (zip [1 2] '[a b c]) ;=> [[1 b] [2 a]]

И действительно, мы получаем пары элементов из xs и ys, составленные вместе, но не по порядку: первый элемент xs соединяется с последним элементом ys, и так далее по строке. Я могу видеть причину проблемы: функция, которую мы производим, потребляет ys, начиная слева, но самое внешнее замыкание (которое называется первым) закрылось над последним элементом xs, поэтому оно не может соединить их справа приказ.

Я думаю, что исправление состоит в том, чтобы каким-то образом выстроить замыкания наизнанку, но я действительно не понимаю, как это сделать. Я с радостью приму решение на Haskell или Clojure.

Я надеюсь на решение формы zip = foldl f x, так что я могу сказать, что это «просто» сокращение. Конечно, я могу перевернуть один из списков, но тогда он будет выглядеть как zip xs ys = foldl f x xs $ reverse ys, что не кажется очень удовлетворительным или чистым.

functional-programming clojure fold haskell
24.01.2015

  • Если вас совсем не заботит эффективность, вы можете использовать init вместо tail и / или ++[a] вместо a:. 25.01.2015
  • В качестве альтернативы вы можете найти реализацию foldr в терминах foldl (для конечных списков) в Интернете. 25.01.2015
  • Что ж, я использую conj в версии Clojure, которая является эффективной версией ++ [a] (с другой структурой данных, чем связанные списки). Это на самом деле не исправляет: вы можете получить либо xs, либо ys в правильном порядке, но не оба очевидным образом, как я могу видеть. 25.01.2015
  • blog.wakatta.jp/blog/2011/11 Я уверен, что / 11 / haskell-foldr-as-foldl дает вам все, что вам нужно. 25.01.2015
  • +1 за то, что серьезно отнеслись к моему вопросу на днях! Рад видеть, что это обсуждение продолжается. Я буду переваривать все эти и другие ответы, которые я нашел, прежде чем комментировать дальнейшие 27.01.2015

Ответы:


1

В Haskell:

-- foldr f z xs == foldl (\r x a-> r (f x a)) id xs z

zip1 xs ys = -- foldr f (const []) xs ys
            foldl (\r x a-> r (f x a)) id xs (const []) ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

Prelude> zip1 [1..9] [100..120]
[(1,100), (2,101), (3,102), (4,103), (5,104), (6,105), (7,106), (8,107) ), (9,108)]

Поскольку Clojure любит добавлять в конец списка, другим вариантом является

zip2 xs ys = foldl f (const []) xs ys
  where
    f r x [] = []
    f r x ys = let (ys0,y) = (init ys, last ys) -- use some efficient Clojure here
               in r ys0 ++ [(x,y)]

Prelude> zip2 [1..9] [100..120]
[(1,112), (2,113), (3,114), (4,115), (5,116), (6,117), (7,118), (8,119) ), (9 120)]

Как вы можете видеть, конец списков находится здесь, а не в начале.

25.01.2015
  • Спасибо! Должен сказать, в Haskell он выглядит более читабельным: refheap.com/37b61066156c2265969b7dd89 27.01.2015
  • @amalloy, обратите внимание, что в этом случае это не просто сворачивание списка. Он сворачивает список для создания функции, а затем применяет функцию. 27.01.2015

    • 2

    Другой эксперт по Clojure указал, что в Clojure это проще сделать, не пытаясь использовать ту же структуру, что и решение foldr в Haskell:

    (defn zip [xs ys]
  (first (reduce
          (fn [[acc rest :as state] itm]
            (if rest
              [(conj acc [itm (first rest)])
               (next rest)]
              state))
          [[] (seq ys)]
          xs)))

    Это просто складывается по паре, первая из которых представляет собой построенную последовательность результатов, а вторая - то, что остается от ys; xs загружаются по одному элементу за раз через сокращение. В Haskell это будет выглядеть так:

    zip' :: [a] -> [b] -> [(a,b)]
zip' xs ys = fst $ foldl f ([], ys) xs
  where f state@(_, []) _x = state
        f (acc, (y:ys)) x = ((acc ++ [(x, y)]), ys)

    за исключением того, что, конечно, acc ++ [(x, y)] гораздо разумнее в Clojure, чем в Haskell, поскольку он эффективен.

    26.01.2015

    3

    Просто внедрите

    reverse = foldl (flip (:)) []

    и примените его ко второму списку.

    24.01.2015
  • Я надеялся на решение вида zip = foldl f x, так что могу сказать, что это просто сокращение. Конечно, я могу перевернуть один из списков, но тогда он будет выглядеть как zip xs ys = foldl f x xs $ reverse ys, что менее удовлетворительно. Я добавлю это к вопросу. 25.01.2015
  • @amalloy Я думаю, вы считаете, что foldl универсален, чтобы быть сильнее, чем есть на самом деле. Обычно в вашем сгибе вычисляются дополнительные данные и некоторые из них отбрасываются или иным образом выполняется некоторая постобработка; например естественный способ выразить функцию, которая выбирает каждый другой элемент списка как свертку, состоит в том, чтобы создать как четные, так и нечетные элементы в виде кортежа. Утверждение состоит в том, что вам не всегда нужен ровно один foldl и ничего больше, а, скорее, единственное, что вам нужно сделать с списками, - это foldl, и это свойство все еще остается верным в моем предлагаемом решении. 25.01.2015
  • Также распространено: использование свертки для создания функции, а затем применение функции, как foldl и foldr определяются в терминах друг друга. 25.01.2015

    • 4

    Эти два оба решения имеют форму (-> (reduce f init x) something), а не просто (reduce f init x). Оба несут с собой контейнер с накопленной последовательностью и некоторым дополнительным состоянием, а затем извлекают последовательность из контейнера. В одном случае контейнер - это закрытие, в другом - вектор.

    Если вы хотите «просто» (reduce f init x), тогда знайте, что у вас уже есть все необходимое состояние в самой накопленной последовательности - ее длина.

    (defn zip* [xs ys] 
  (let [xs (vec xs)
        f (fn [a y]
            (if (contains? xs (count a))
              (conj a [(xs (count a)) y])
              a))]
    (reduce f [] ys)))
    28.01.2015
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..