3

データ構造をネストすると、それらを掘り下げるためのコードを手動で記述していることに気付きました。このような：

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

それは私にそれを打つ

  1. 私はそれが期待した場所のリストを見つけることを理解しています...何か他のもの
  2. これを修正する方法がわかりません-反復が目的であると思っていたとしても、繰り返し適用するコードを書く必要がありますか？
  3. これは「持ち上げる」という概念に似ているように見えますが、その直感をどのように適用するかはわかりません。
4

2 に答える 2

9

問題は、これらの「反復」のタイプが異なることです。反復ごとに、追加レベルのネストが取得されるため、

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)]
于 2012-10-18T03:09:18.187 に答える
3

の種類について考えてみてください(iterate map f) !! n。a -> afor n = 0、[a] -> [a]for n = 1、[[a]] -> [[a]]for-である必要があります。一般に、この式のタイプは。の値にn = 2依存する必要があります。しかし、Haskellは依存型の言語ではないため、これを行うことは不可能です。n

于 2012-10-18T03:09:48.340 に答える