Я застрял в императивном мышлении программирования и не понимаю
Haskell, как я должен?
Вы не застряли, по крайней мере, я на это не надеюсь. То, что вы испытываете, абсолютно нормально. Когда вы работали с императивными языками, вы учились (возможно, не зная), чтобы увидеть проблемы программирования с очень конкретной точки зрения, а именно с точки зрения машины Ван Неймана.
Если у вас есть проблема, скажем, составления списка, который содержит некоторую последовательность чисел (допустим, мы хотим, чтобы первые 1000 четных чисел), вы сразу подумаете: реализация связанного списка (возможно, из стандартной библиотеки вашего язык программирования), цикл и переменную, которую вы установили бы в качестве начального значения, а затем на некоторое время вы бы зациклились, обновив переменную, добавив 2 и поместив ее в конец списка.
Видите, как вы в основном думаете обслуживать машину? Места памяти, петли и т. Д.!
В императивном программировании каждый думает о том, как манипулировать определенными ячейками памяти в определенном порядке, чтобы постоянно находить решение . (Это, между прочим, одна из причин, почему новичкам трудно научиться программированию.) Программисты просто не используют для решения проблем, сводя их к последовательности операций с памятью. Почему они должны? Но как только вы узнали это, вы иметь власть - в императивном мире. Для функционального программирования вам нужно отучиться от этого.)
В функциональном программировании, особенно в Haskell, вы просто указываете закон построения списка. Поскольку список является рекурсивной структурой данных, этот закон, конечно, также рекурсивен. В нашем случае мы могли бы, например, сказать следующее:
constructStartingWith n = n : constructStartingWith (n+2)
И почти готово! Чтобы прийти к нашему окончательному списку, нам нужно только сказать, с чего начать и сколько мы хотим:
result = take 1000 (constructStartingWith 0)
Обратите внимание, что в библиотеке доступна более общая версия constructStartingWith, она называется iterate и принимает не только начальное значение, но и функцию, которая делает следующий элемент списка из текущего:
iterate f n = n : iterate f (f n)
constructStartingWith = iterate (2+) -- defined in terms of iterate
Другой подход - предположить, что у нас был другой список, из которого мы могли бы легко составить список. Например, если бы у нас был список первых n целых чисел, мы могли бы легко превратить его в список четных целых чисел, умножив каждый элемент на 2. Теперь список первых 1000 (неотрицательных) целых чисел в Haskell просто
[0..999]
И есть функция map, которая преобразует списки, применяя данную функцию к каждому аргументу. Функция, которую мы хотим, состоит в удвоении элементов:
double n = 2*n
Таким образом:
result = map double [0..999]
Позже вы узнаете больше ярлыков. Например, нам не нужно определять double, но мы можем использовать раздел: (2*) или мы могли бы написать наш список напрямую как последовательность [0,2..1998]
Но не зная этих трюков, вы не должны чувствовать себя плохо! Основная задача, с которой вы сейчас сталкиваетесь, заключается в разработке менталитета, в котором вы видите , что проблема построения списка первых 1000 четных чисел состоит из двух этапов: выглядит и б) взять определенную часть этого списка. Как только вы начинаете думать таким образом, вы делаете , даже если вы все еще используете рукописные версии iterate и take.
Возвращаясь к проблеме Эйлера: здесь мы можем использовать метод сверху вниз (и несколько основных функций манипулирования списком, о которых действительно нужно знать: head, drop, filter, any). Во-первых, если у нас уже есть список простых чисел, мы можем просто отбросить первую 1000 и взять голову остальных, чтобы получить 1001-е:
result = head (drop 1000 primes)
Мы знаем, что после отбрасывания любого числа элементов в бесконечный список все равно останется непустой список для выбора head, следовательно, использование head здесь оправдано. Если вы не уверены, что существует более 1000 простых чисел, вы должны написать что-то вроде:
result = case drop 1000 primes of
[] -> error "The ancient greeks were wrong! There are less than 1001 primes!"
(r:_) -> r
Теперь самое сложное. Не зная, как поступить, мы могли бы написать псевдокод:
primes = 2 : {-an infinite list of numbers that are prime-}
Мы точно знаем, что 2 - это первое простое число, так сказать, базовый случай, поэтому мы можем записать его. Незаполненная часть дает нам возможность задуматься. Например, список должен начинаться с некоторого значения, которое больше 2 по очевидной причине. Отсюда уточняется:
primes = 2 : {- something like [3..] but only the ones that are prime -}
Теперь, это тот момент, когда возникает шаблон, который нужно научиться распознавать. Это, безусловно, список filter, отредактированный предикатом , а именно, простотой (не имеет значения, что мы еще не знаем, как проверить простоту, важна логическая структура. (И мы можем быть уверены, что тест на первичность возможен!)). Это позволяет нам писать больше кода:
primes = 2 : filter isPrime [3..]
См? Мы почти закончили. В 3 этапа мы сократили довольно сложную задачу таким образом, чтобы все, что осталось написать, было довольно простым предикатом.
Опять же, мы можем написать в псевдокоде:
isPrime n = {- false if any number in 2..n-1 divides n, otherwise true -}
и может это уточнить. Поскольку это уже почти haskell, это слишком просто:
isPrime n = not (any (divides n) [2..n-1])
divides n p = n `rem` p == 0
Обратите внимание, что мы еще не занимались оптимизацией. Например, мы можем сразу создать список для фильтрации, который будет содержать только нечетные числа, поскольку мы знаем, что четные не являются простыми. Что еще более важно, мы хотим сократить количество кандидатов, которых мы должны попробовать в isPrime. И здесь требуются некоторые математические знания (то же самое будет верно, если вы запрограммируете это на C ++ или Java, конечно), что говорит нам, что достаточно проверить, является ли n, который мы проверяем, делимым на любое простое число и что нам не нужно проверять делимость на простые числа, площадь которых больше n. К счастью, мы уже определили список простых чисел и можем выбрать набор кандидатов оттуда! Я оставляю это как упражнение.
Позже вы узнаете, как использовать стандартную библиотеку и синтаксические сахара, такие как разделы, списки и т. Д., И постепенно откажетесь от написания собственных базовых функций.
Даже позже, когда вам снова придется что-то делать на императивном языке программирования, вам будет очень трудно жить без бесконечных списков, функций высшего порядка, неизменяемых данных и т. Д.
Это будет так же сложно, как вернуться из Си в Ассемблер.
Веселись!