반복적으로 맵을 적용하기 위해 반복을 사용할 수없는 이유는 무엇입니까?

Question

중첩 된 데이터 구조가있을 때 필자는 수동으로 코드를 작성하여이를 조사했습니다. 이처럼 :

Prelude> let t f n = (iterate map f) !! n 

<interactive>:35:22: 
    Occurs check: cannot construct the infinite type: b0 = [b0] 
    Expected type: (a0 -> b0) -> a0 -> b0 
     Actual type: (a0 -> b0) -> [a0] -> [b0] 
    In the first argument of `iterate', namely `map' 
    In the first argument of `(!!)', namely `(iterate map f)' 

그 날

을하는 것이 파업 : 그래서 내가 자동으로 고차 함수를 사용하여 내 중첩 된 데이터 구조로 탐구하는 기능을 구성 할 수 있어야한다고 나에게 발생

--one level 
Prelude> map (*2) [1,2,3] 
[2,4,6] 

--nested two levels 
Prelude> let t2 = map $ map (*2) 
Prelude> t2 [[1,2,3],[4,5,6]] 
[[2,4,6],[8,10,12]] 

--nested three levels 
Prelude> let t3 = map $ map $ map (*2) 
Prelude> t3 [[ [1,2,3],[4,5,6] ],[ [1,2,3],[4,5,6] ]] 
[[[2,4,6],[8,10,12]],[[2,4,6],[8,10,12]]] 

1. 내가이 예상 한 위치에 그것의 목록을 발견 ... 나는이 문제를 해결하는 방법을 모르는
2. 다른 것을 이해 - 나는 영장해야 전자 코드 반복 된 응용 프로그램을 할 비록 its 생각했던 iterate 무엇입니까?
3. 이것은 "리프팅"개념과 비슷하지만 그 직감을 적용하는 방법을 모르겠습니다.

Answer 1

문제는 이러한 "반복"에 다른 유형이 있다는 것입니다. 당신이

t f 0 :: a -> b 
t f 1 :: [a] -> [b] 
t f 2 :: [[a]] -> [[b]] 

그러나 iterate :: (a -> a) -> a -> [a]이 반복 모두 같은 유형이 있어야 할 것 있도록 각 반복의 경우, 중첩의 여분 수준을 얻는다. 실제로, 위의 직접 구현은 리턴 유형이 n 값에 의존하기 때문에 몇 가지 종속 유형을 필요로합니다.

좋은 이유가없는 한 간단하게 유지하고 필요한 수의 map 전화를 작성하는 것이 좋습니다. Template Haskell을 사용하여 생성 할 수도 있지만, 이것은 가치있는 것보다 더 어려울 것입니다.

그러나 중첩 된 데이터 구조가 복잡한 경우 SYB을 조사하면 이러한 변환을 중첩 된 구조에 적용하는 일반적인 방법을 자동으로 처리 할 수 ​​있습니다.

> import Data.Generics 
> let t x = everywhere (mkT (*2)) x 
> :t t 
t :: Data a => a -> a 
> t [2,4,6] 
[4,8,12] 
> t [[2,4,6],[8,10,12]] 
[[4,8,12],[16,20,24]] 
> t (Just [(1, 2, 3), (4, 5, 6)]) 
Just [(2,4,6),(8,10,12)] 

Answer 2

이 (iterate map f) !! n의 유형에 대해 생각 :

여기에 빠른 예입니다. 당신은 n = 2에 대한 n = 1에 대한 n = 0에 대한 a -> a, [a] -> [a], [[a]] -> [[a]]되고 싶어 - 일반적으로,이 표현의 유형이 값 n의에 의존합니다. 하스켈에서는 의존형 언어가 아니기 때문에 불가능합니다.