Zmagam się z Haskellem i ideą używania rekurencji do iterowania rzeczy.W jaki sposób ten fragment zostanie przetłumaczony na Haskell?
Na przykład, w jaki sposób
// 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
przekładają się na paradygmacie 'funkcjonalnej'? Wszelkie wskazówki będą mile widziane.
Idąc krok po kroku:
list2 = list of numbers
Weźmiemy to jak dana, więc list2 nadal jest tylko lista numerów.
for i from 0 to N // N being a positive integer
Poprawny sposób to zrobić w Haskell jest na ogół z listy. Lenistwo oznacza, że wartości będą obliczane tylko wtedy, gdy są używane, więc przechodzenie przez listę od 0 do N kończy się tak samo jak pętla, którą tu masz. Więc tylko [0..n] załatwi sprawę; musimy tylko dowiedzieć się, co z tym zrobić.
for each number in list2
Biorąc pod uwagę „dla każdego”, możemy wywnioskować, że musimy przechodzić całość list2 tutaj; co z tym robimy, jeszcze nie wiemy.
if number == i, add to list1
Budujemy list1 jak idziemy, tak idealnie, że chcemy być ostateczny wynik wyrażenia. Oznacza to również, że na każdym etapie rekurencyjnym chcemy, aby wynik był list1, który mamy "do tej pory". Aby to zrobić, musimy upewnić się, że wyniki każdego kroku są przekazywane razem z nami.
więc schodzimy do mięsa IT:
Funkcja filter znajdzie wszystkie elementy na liście pasujących jakieś orzeczenie; użyjemy tutaj filter (== i) list2, aby znaleźć to, czego szukamy, a następnie dołączyć do wyniku poprzedniego kroku. Tak więc każdy krok będzie wyglądał następująco:
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
To obsługuje pętlę wewnętrzną. Odwracając się na zewnątrz, musimy uruchomić to dla każdej wartości i z listy [0..n], przy czym wartość list1 jest przekazywana w każdym kroku.To jest dokładnie to, co krotnie funkcje są dla iw tym przypadku step jest dokładnie to, czego potrzebujemy dla lewego fałdu:
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]
Jeśli zastanawiasz się, gdzie rekurencji jest filter i foldl robią to za nas oboje . Zasadniczo lepiej unikać bezpośredniej rekursji, gdy istnieją funkcje wyższego poziomu, aby zrobić to za Ciebie.
Powiedział, że tu jest głupi algorytm na wiele sposobów, ale nie chce się w to, bo wydawało się, że to odciągnąć od rzeczywistego pytanie więcej niż miałoby to pomóc.
Niestety, ale nie mogę pomóc, ale lepiej użyć algorytmu ...
let goodNumber n = (0 <= n && n < N)
let list1 = sort (filter goodNumber list2)
Edit: Z perspektywy czasu jest to trochę przesada, ponieważ PO próbuje wdrożyć sortowanie algo w pierwszej kolejności.
let list1 = sort [a | a<-list2, a>=0, a<=N]
a<-list2 podnosi każda liczba listy2 a>=0, a<=N Sprawdź, czy wybrał numer spełnia wszystkie te warunki , jeżeli spełnione są warunki, a zostaje wprowadzone do nowej listy Gdy wszystkie elementy listy2 zostały w ten sposób sprawdzane i umieścić na nowej liście, sortujemy na tym Wynikowa lista jest przypisana do listy1
Dlaczego nie użyć 'concatMap' zamiast składania jawnego kroku konkatenacji? – bdonlan
Należy zauważyć, że w tym przypadku można użyć funkcji sprawdzania list: [numer | i <- [1..N], numer <-list2, i == numer], który jest bezpośrednim tłumaczeniem Twojego pseudokodu. – ysdx
Dzięki za wspaniałą odpowiedź. Zdaję sobie sprawę, że opublikowany przeze mnie fragment jest dziwny ... Drastycznie ogoliłem wszelkie znaczenie z tego. Jest to część ćwiczenia sortowania radix, które robię. –