하스켈의 함수에 대한 루핑

Question

나는 이걸로 당황 스럽다. 하스켈의 루프 - 정렬 - 물건 - 어떻게 쓰는지 알아낼 수 없다. 기본적으로 세 가지 기능을 정의했습니다. , 리플 및 셔플입니다.

riffle [1,2,3] [4,5,6] = [1,4,2,5,3,6] 

을 그리고 셔플의 분할의 양 riffling을 반복하는 것입니다

split :: [a] -> ([a],[a]) 
split xs = splitAt (length xs `div` 2) xs 

riffle :: [a] -> [a] -> [a] 
riffle xs [] = xs 
riffle [] ys = ys 
riffle (x:xs) (y:ys) = x:y:riffle xs ys 

shuffle :: Int -> [a] -> [a] 
shuffle 0 xs = xs 
shuffle n xs = shuffle (n-1) (riffle a b) 
    where (a, b) = split xs 

은 기본적으로 절반의 목록을 분할 예를 들어, 그래서 리플이 두 목록 '인터레이스'로 가정된다 분할 목록 항목. 이제는 함수를 정의해야합니다. 을 반복하여 원래 목록을 다시 가져 오는 데 걸리는 셔플 반복 횟수를 출력합니다.

난 그냥 당신이 셔플을 통해 루프를 수행 할 수있는 방법으로 붙어있어

repeats :: [Int] -> Int 

... 나는 그것이 지능형리스트와 함께 할 수있는 뭔가가 생각하지만 난 아무것도 얻을 수 없습니다 : 함수는 같은 정의 . 아직 람다 표현식을 시험해 보았지만 필자는 그것이 필요하다고 생각하지 않는다. 그건 그렇고, 셔플은 항목 수가 짝수 인 목록에서 수행해야합니다. 어떤 아이디어?

Answer 1

이 문제를 해결하는 한 가지 방법은 게으름을 이용하고 iterate을 사용하여 입력의 반복 된 셔플의 무한한 목록을 생성하는 것입니다.

> iterate (uncurry riffle . split) "ABCDEF" 
["ABCDEF","ADBECF","AEDCBF","ACEBDF","ABCDEF","ADBECF","AEDCBF","ACEBDF", ...] 

목록의 첫 번째 요소는 원래 하나입니다, 그래서 우리는 tail로, 다음 원래 달랐다 사람을 얻을 수 takeWhile를 사용하는 것이 놓습니다.

> takeWhile (/= "ABCDEF") . tail $ iterate (uncurry riffle . split) "ABCDEF" 
["ADBECF","AEDCBF","ACEBDF"] 

지금, 당신은 단지 그 목록의 length을 가지고 셔플 필요한 수를 얻기 위해 하나를 추가해야합니다.

Answer 2

많은 경우에 "루프"가 아닌 무한한 목록을 사용할 수 있습니다. 이것은 그들 중 하나입니다. 당신이 진보적 인 셔플을 얻을 후 시작 목록 "으로 반복 셔플"을 적용하는 경우

전주곡 기능은 "반복은"반복 그래서

iterate f x = [x, f x, f (f x), f (f (f x)) ....] 

(메모리) 때문에, 값에 함수를 적용한다. 그런 다음 takeWhile을 사용하여 목록에서 시작 지점과 동일한 첫 번째 항목을 찾은 다음 "길이"를 찾아 길이를 찾습니다.

Answer 3

하스켈에서 반복은 루핑을 사용하는 대신 재귀를 사용하여 가장 일반적으로 표현됩니다.

이것은 종종 반복을 수행하는 방법을 알려주는 내부 함수를 사용하여 수행 한 다음 적절한 인수를 사용하여 내부 함수를 호출하기 만하면됩니다.

아마도 다음 코드에서 차이를 채울 수 있습니까?

repeats xs = iter 1 (...) where 
    iter n ys = if ys == xs 
     then n 
     else iter (...) (...) 

다른 방법은 반복 초기 인자에 함수를 적용 고차 함수 iterate를 사용 하스켈 게으름 악용 무한리스트를 수행하는 것이다

repeats xs = (...) $ takeWhile (...) $ iterate (shuffle 1) (...) 

iterate를 있지만 무한한 목록을 반환 할 때, 우리는 오직 그것의 한정된 부분 만 사용할 것이고 그래서 우리는 무한 루프에 빠지지 않습니다.