Использование складывания в определяющих функциях - PullRequest
Новая
       14

Использование складывания в определяющих функциях

0 голосов
/ 06 февраля 2019

Я познакомился с использованием сгиба в определении функции.У меня есть идея, как это работает, но я не уверен, почему это нужно делать.Для меня это похоже на простое имя типа данных и значения данных ... Было бы здорово, если бы вы могли показать мне примеры, где важно использовать сложение. 

data List a = Empty | (:-:) a (List a)

--Define elements
List a :: *
[] :: List a
(:) :: a -> List a  -> List a

foldrList :: (a -> b -> b) -> b -> List a -> b
foldrList f e Empty = e
foldrList f e (x:-:xs) = f x (foldrList f e xs)

Ответы [ 2 ]

0 голосов
/ 06 февраля 2019

Функции высшего порядка, такие как foldr, foldl, map, zipWith и т. Д.захватывать общие шаблоны рекурсии, чтобы избежать написания рекурсивных определений вручную.Это делает ваш код более высокоуровневым и более читабельным: вместо того, чтобы переходить по коду и делать выводы о том, что делает рекурсивная функция, программист может рассуждать о композициях компонентов более высокого уровня.

Для несколько экстремальныхНапример, рассмотрим рекурсивный расчет стандартного отклонения вручную: 

standardDeviation numbers = step1 numbers
  where

    -- Calculate length and sum to obtain mean
    step1 = loop 0 0
      where
        loop count sum (x : xs) = loop (count + 1) (sum + x) xs
        loop count sum [] = step2 sum count numbers

    -- Calculate squared differences with mean
    step2 sum count = loop []
      where
        loop diffs (x : xs) = loop ((x - (sum / count)) ^ 2 : diffs) xs
        loop diffs [] = step3 count diffs

    -- Calculate final total and return square root
    step3 count = loop 0
      where
        loop total (x : xs) = loop (total + x) xs
        loop total [] = sqrt (total / count)

(Чтобы быть справедливым, я немного переборщил, также указав суммирование, но это примерно так, как это обычно делается в императивном языке).- зацикливание вручную.)

Теперь рассмотрим версию, использующую композицию вызовов стандартных функций, некоторые из которых более высокого порядка: 

standardDeviation numbers          -- The standard deviation
  = sqrt                           -- is the square root
  . mean                           -- of the mean
  . map (^ 2)                      -- of the squares
  . map (subtract                  -- of the differences
      (mean numbers))              --   with the mean
  $ numbers                        -- of the input numbers
  where                            -- where
    mean xs                        -- the mean
      = sum xs                     -- is the sum
      / fromIntegral (length xs)   -- over the length.

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

Более того, sum, map и length могут быть реализованы в терминах сгибов, а также многих других стандартных функций.как product, and, or, concat и т. д.Складывание является чрезвычайно распространенной операцией не только для списков, но и для всех типов контейнеров (см. Класс типов Foldable), поскольку оно захватывает шаблон вычисления чего-то постепенно для всех элементов контейнера.

Последняя причинаиспользование сгибов вместо ручной рекурсии является производительностью: благодаря лени и оптимизациям, которые GHC знает, как выполнять при использовании функций на основе fold, компилятор может объединить серию сгибов (отображений и т. д.) в один циклво время выполнения.

0 голосов
/ 06 февраля 2019

Идея складывания - мощная.Функции сгиба (foldr и foldl в базовой библиотеке Haskell) происходят из семейства функций, называемых функциями высшего порядка (для тех, кто не знает, - это функции, которые принимают функции в качестве параметров или возвращают функции в качестве своихвывод).

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

Большее повторное использование кода может быть достигнуто при свертывании из-за характера передачи в функциюв качестве параметра.Если в программе есть какое-то поведение, на которое влияет передача логического или перечислимого значения, то это поведение можно абстрагировать в отдельную функцию.Затем отдельную функцию можно использовать в качестве аргумента для свертывания.Это обеспечивает большую гибкость и простоту (поскольку есть 2 более простых функции по сравнению с 1 более сложной функцией).

Функции высшего порядка также важны для монад .

комментарии к этому вопросу, а также для разнообразия и информативности.

...