이 스 니펫은 어떻게 하스켈로 번역됩니까?

Question

나는 하스켈과 재귀를 사용하여 재귀를 반복하는 것에 대해 고심하고있다.

예를 들어

, 어떻게

// 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 

는 '기능적 패러다임'으로 번역 할 것인가? 모든 지침을 부탁드립니다.

Answer 1

가는 단계 :

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 

이는 내부 루프를 처리합니다. 바깥으로 되돌아 가서 각 단계마다 list1 값이 전달되는 목록 [0..n]에서 각 값 i에 대해이 작업을 실행해야합니다.재귀이고, 모두 filter 및 foldl 우리를 위해 그 일을하는

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] 

당신이 궁금해하는 경우 :이 함수가 있으며,이 경우 step 우리는 왼쪽 배에 필요한 정확히 배 정확히 . 대개의 경우, 더 높은 수준의 함수가있을 때 직접 재귀를 피하는 것이 좋습니다.

---

여기 알고리즘은 여러 가지 방법으로 바보 말했다,하지만 나는 그것이 도움이 될 것보다 더 실제 질문에서 방해 할 것처럼 보였다 때문에 들어갈 싶지 않았다.

Answer 2

미안하지만, 나는 도움이되지만 더 나은 알고리즘을 사용할 수 없습니다 ...

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

---

편집 : OP는을 구현하기 위해 노력하고 이후이 과잉의 조금이다 지나고 우선 알 고를 분류. 단계별로

Answer 3

let list1 = sort [a | a<-list2, a>=0, a<=N] 

a<-list2 픽업리스트 2의 각 번호는 a>=0, a<=N 검사가 포착 수는 조건이 충족 될 경우, A는리스트 2의 모든 요소 따라서 검사 한 후에는 새 목록 에 투입되고 이러한 모든 조건을 충족하는 경우 새로운리스트에 넣으면, 우리는 이것에 대해 정렬을한다. 결과리스트가 list1에 할당된다.