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

Question

Насколько хорошо «чистое» функциональное программирование для базовых рутинных реализаций, например, сортировка списков, сопоставление строк и т. д .?

Обычно такие базовые функции реализуются в базовом интерпретаторе любого функционального языка, что означает, что они будут написаны на императивном языке (c / c ++). Хотя есть много исключений ..

По крайней мере, я хотел бы спросить: насколько сложно имитировать императивный стиль при кодировании на «чистом» функциональном языке?

Answer 1

Насколько хорош «чистый» функционал? программирование для основной рутины реализации, например сортировка списка, сопоставление строк и т. д .?

Очень. Я сделаю твои проблемы в Хаскеле, и я буду немного многословен об этом. Моя цель состоит не в том, чтобы убедить вас, что задача может быть решена в 5 символов (возможно, в J!), А в том, чтобы дать вам представление о конструкциях.

import Data.List -- for `sort`
stdlistsorter :: (Ord a) => [a] -> [a]
stdlistsorter list = sort list

Сортировка списка с использованием функции sort из Data.List

import Data.List -- for `delete`
selectionsort :: (Ord a) => [a] -> [a]
selectionsort [] = []
selectionsort list = minimum list : (selectionsort . delete (minimum list) $ list)

Реализация сортировки выбора.

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted  

Быстрая реализация сортировки.

import Data.List -- for `isInfixOf`
stdstringmatch :: (Eq a) => [a] -> [a] -> Bool
stdstringmatch list1 list2 = list1 `isInfixOf` list2

Соответствие строк с использованием функции isInfixOf из Data.list

Обычно реализуют такие базовые функции в базовом интерпретаторе любого функционального языка, который означает, что они будут написаны в императивный язык (с / с ++). Хотя Есть много исключений ..

Зависит. Некоторые функции более естественно выражены императивно. Тем не менее, я надеюсь, что убедил вас, что некоторые алгоритмы также выражены естественным образом функциональным образом.

По крайней мере, я хочу спросить: насколько сложно это подражать императивному стилю при кодировании в «чистый» функционал язык

Это зависит от того, как сильно вы находите Монады в Хаскеле. Лично мне трудно понять.

Answer 2

1) Хорошо по какому стандарту? Какие свойства вы желаете?

Сортировка списка? Легко. Давайте сделаем Quicksort в Haskell:

sort [] = []
sort (x:xs) = sort (filter (< x) xs) ++ [x] ++ sort (filter (>= x) xs)

Этот код обладает тем преимуществом, что его чрезвычайно легко понять. Если список пуст, он отсортирован. В противном случае вызовите первый элемент x, найдите элементы меньше x и отсортируйте их, найдите элементы больше x и отсортируйте их. Затем объедините отсортированные списки с х в середине. Попробуйте сделать это понятным в C ++.

Конечно, Mergesort намного быстрее сортирует связанные списки, но код также в 6 раз длиннее.

2) Очень легко реализовать императивный стиль, оставаясь при этом чисто функциональным. Суть императивного стиля - последовательность действий. Действия чередуются в чистом виде с помощью монад. Суть монад заключается в обязательной функции:

(Monad m) => (>>=) :: m a -> (a -> m b) -> m b

Эта функция существует в C ++ и называется ;.

Последовательность действий в Хаскеле, например, записана так:

putStrLn "What's your name?" >>=
  const (getLine >>= \name -> putStrLn ("Hello, " ++ name))

Некоторый синтаксический сахар доступен, чтобы сделать этот вид более обязательным (но учтите, что это точно такой же код ):

do {
  putStrLn "What's your name?";
  name <- getLine;
  putStrLn ("Hello, " ++ name);
}

Answer 3

Я думаю, что «алгоритмы» (например, тела методов и базовые структуры данных) - это то место, где функциональное программирование лучше всего. Если предположить, что функциональное программирование лучше всего зависит от ввода-вывода и состояния, то это алгоритмы и структуры данных, которые часто приводят к более короткому / простому / более чистому коду, чем вы получили бы с помощью императивного решения. (Не подражайте императивному стилю, стиль FP лучше подходит для большинства задач такого типа.)

Вы хотите, чтобы императивные вещи иногда имели дело с IO или низкоуровневой производительностью, и вы хотите, чтобы ООП разделял высокоуровневый дизайн и архитектуру большой программы, но «в маленькой», где вы пишете большую часть своего кода, FP - это победа.

Смотри также

Как функциональное программирование влияет на структуру вашего кода?

Answer 4

Почти все функциональные языки программирования имеют некоторую конструкцию, допускающую императивное кодирование (например, do в Haskell). Есть много проблемных областей, которые не могут быть решены с помощью «чистого» функционального программирования. Одним из них являются сетевые протоколы, например, когда вам требуется серия команд в правильном порядке. И такие вещи плохо поддаются чисто функциональному программированию.

Я должен согласиться с Lothar , однако, сортировка списков и сопоставление строк на самом деле не являются примерами, которые вам необходимо решить в обязательном порядке. Для таких вещей существуют хорошо известные алгоритмы, и они уже могут быть эффективно реализованы на функциональных языках.

Answer 5

Я не знаю о сортировке списка, но вам будет сложно загрузить язык без какого-либо совпадения строк в компиляторе или во время выполнения. Так что вам нужна эта рутина для создания языка. Поскольку нет необходимости писать дважды один и тот же код дважды, когда вы создаете библиотеку для сопоставления строк в языке, вы вызываете код, написанный ранее. Степень, в которой это происходит в последующих выпусках, будет зависеть от того, насколько языком является сам хостинг, но если это не является сильной целью разработки, не будет никаких причин его менять.

Answer 6

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

Помните, что внутренняя часть интерпретатора или программного обеспечения ВМ настолько близка к металлу и критична по производительности, что вы даже должны подумать о переходе на уровень сборки и подсчете тактов для каждой инструкции (как, например, Smalltalk Dophin делает это, и результаты впечатляет). Процессоры являются обязательными.

Но нет никаких проблем с выполнением всей базовой реализации алгоритма - вы упомянули, что НЕ низкий уровень, - это основы.