Как этот фрагмент перевести на Haskell? - PullRequest
Новая
       16

Как этот фрагмент перевести на Haskell?

8 голосов
/ 20 сентября 2011

Я борюсь с Haskell и идеей использования рекурсии для итерации по вещам.

Например, как бы 

// this might seem silly but I need to do it
list1 = empty list
list2 = list of numbers
for i from 0 to N // N being a positive integer
    for each number in list2
        if number == i, add to list1

переводить в «функциональную парадигму»? Любое руководство будет оценено.

Ответы [ 3 ]

10 голосов
/ 20 сентября 2011

Извините, но я не могу не использовать лучший алгоритм ... 

let goodNumber n = (0 <= n && n < N)
let list1 = sort (filter goodNumber list2)

Редактировать: Оглядываясь назад, это немного излишне, поскольку ОП пытался реализоватьалгоритм сортировки в первую очередь.

9 голосов
/ 20 сентября 2011

Шаг за шагом: 

list2 = list of numbers

Мы примем это как данность, поэтому list2 - это просто список чисел. 

for i from 0 to N // N being a positive integer

Правильный способ сделать это в Хаскеле, как правило, с помощью списка. Ленивость означает, что значения будут вычисляться только при использовании, поэтому обход списка от 0 до N заканчивается тем же, что и цикл, который у вас здесь есть. Итак, просто [0..n] сделает свое дело; нам просто нужно выяснить, что с этим делать. 

for each number in list2

Учитывая "для каждого", мы можем сделать вывод, что нам нужно пройти здесь по полноте list2; что мы с ним делаем, пока не знаем. 

if number == i, add to list1

Мы строим list1 на ходу, поэтому в идеале мы хотим, чтобы это был конечный результат выражения. Это также означает, что на каждом рекурсивном шаге мы хотим, чтобы результат был list1, который мы имеем «до сих пор». Чтобы сделать это, нам нужно убедиться, что мы передаем результат каждого шага по ходу.

Итак, приступим к мясу:

Функция filter находит все элементы в списке, соответствующие некоторому предикату; мы будем использовать filter (== i) list2 здесь, чтобы найти то, что нам нужно, затем добавим это к результату предыдущего шага. Поэтому каждый шаг будет выглядеть так: 

step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2

Это обрабатывает внутренний цикл. Возвращаясь назад, нам нужно запустить это для каждого значения i из списка [0..n], причем значение list1 передается на каждом шаге. Это как раз то, для чего нужны функции сгиба, и в этом случае step это именно то, что нам нужно для левого сгиба: 

list2 :: (Num a) => [a]
list2 = -- whatever goes here...

step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2

list1 :: (Num a) => a -> [a]
list1 n = foldl step [] [0..n]

Если вам интересно, где находится рекурсия, то и filter, и foldl делают это для нас. Как правило, лучше избегать прямой рекурсии, когда для этого есть функции более высокого уровня.

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

0 голосов
/ 01 октября 2011 
let list1 = sort [a | a<-list2, a>=0, a<=N]

a<-list2 подбирает каждый номер списка2 a>=0, a<=N проверить, соответствует ли выбранный номер ВСЕМ этим условиям если условия выполнены, a заносится в новый список После того, как все элементы list2 были проверены и помещены в новый список, мы делаем сортировку по этому Результирующий список назначается списку 1

...