爲什麼我不能使用迭代來重複應用地圖？

我已經意識到，當我嵌套數據結構時，我一直在手動編寫代碼來深入研究它們。就像這樣：爲什麼我不能使用迭代來重複應用地圖？

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

所以它發生，我認爲我應該能夠自動地構建功能，使用高階函數鑽研我的嵌套的數據結構：

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)'

它給我的印象是

我理解它找到一個列表，其中，預計...別的
我不知道如何解決這一問題 - 我應該令狀e代碼做重複的應用程序，即使這是我認爲迭代的目的？
這似乎與「提升」的概念類似 - 但我不知道如何應用這種直覺。

來源

2012-10-18 nont

問題是這些「迭代」有不同的類型。對於每次迭代，你會得到嵌套了一層額外的，所以你要

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

但iterate :: (a -> a) -> a -> [a]要求迭代都具有相同的類型。實際上，直接執行上述操作需要某種形式的依賴類型，因爲返回類型取決於值n。

除非你有充分的理由不這麼做，否則我建議保持簡單，只需要寫出所需數量的map調用。可以使用模板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)]

來源

2012-10-18 03:09:18 hammar

謝謝！作爲一個相對的Haskell noob，這可能是我第一次碰到一個表示語言限制的錯誤，而不僅僅是我理解的限制！現在...學習一些Agda :) – nont

它不是不可能的 - 它不建議新手嘗試這樣的事情，因爲它們不是慣用的。如果您有充分的理由這樣做，那麼您應該明確地詢問是否可以使用高級功能，如類型級別的數字。如果可以在Agda中表達，那麼可能有可能在Haskell中表達，因爲它有很多類型級別的機器，通常以依賴型語言存在。 – nponeccop

想想的(iterate map f) !! n類型。你希望它是a -> a爲n = 0，[a] -> [a]爲n = 1，[[a]] -> [[a]]爲n = 2 - 一般情況下，你想這個表達式的類型依賴於價值n。但是這在Haskell中是不可能的，因爲它不是一種依賴類型的語言。

來源

2012-10-18 03:09:48

爲什麼我不能使用迭代來重複應用地圖？

回答

相關問題