8

概要: これは Miranda 試験の過去の試験問題ですが、構文は Haskell に非常に似ています。

質問: 次の式の型とその機能は何ですか? (関数 length と swap の定義は以下に示します)。

(foldr (+) 0) . (foldr ((:) . length . (swap (:) [] )) [])

length [] = 0

length (x:xs) = 1 + length xs

swap f x y = f y x

ノート：

Haskell 構文でお気軽に返信してください - 星をポリタイプとして使用して申し訳ありませんが、誤って Haskell に変換したくありませんでした。基本的に、1 つの変数の型が * で、もう 1 つの変数の型が * である場合、それらは任意の型にすることができますが、両方とも同じ型でなければならないことを意味します。** がある場合、* と同じ型を持つことができますが、その必要はないことを意味します。Haskellの使い方でa,b,cなどに相当すると思います。

私のこれまでの仕事

長さの定義から、何かのリストの長さを見つけることができるので、これは次のようになります

length :: [*] -> num.

定義から、swap は関数と 2 つのパラメーターを取り、2 つのパラメーターがスワップされた関数を生成すると思います。

swap :: (* -> ** -> ***) -> ** -> [*] -> ***

foldr は二項関数 (plus のような) 開始値とリストを取り、その関数を使用してリストを右から左に折り畳みます。これは与える

foldr :: (* -> ** -> **) -> ** -> [*] -> **)

関数合成では右結合であることを知っています。たとえば、最初のドット (.) の右側にあるものはすべて、最初のフォルダーへの引数として与えられるため、リストを生成する必要があります。

foldr 関数は単一の値 (リストを折りたたんだ結果) を出力するので、戻り値の型はポリタイプのリストではなく、ある種のポリタイプになることがわかります。

私の問題

ここからどこへ行くのか本当にわかりません。swap が別の引数を受け取る必要があることがわかりますが、この部分的な適用は全体が関数であることを意味しますか? 私はかなり混乱しています！

4

2 に答える 2

9

あなたはすでに答えを得ています。一度にすべてを簡単に確認できるように、導出を段階的に書き留めます。

xxf xs = foldr (+) 0 . foldr ((:) . length . flip (:) []) [] $ xs
       = sum         $ foldr ((:) . length . (: []))      []   xs
       = sum         $ foldr (\x -> (:) (length [x]))     []   xs
       = sum         $ foldr (\x r ->    length [x]:r)    []   xs
       = sum         $ map   (\x   ->    length [x]  )         xs
       = sum                            [length [x]  |    x <- xs]  
       = sum                            [ 1          |    x <- xs]
--     = length xs
xxf :: (Num n) => [a] -> n

そのため、ミランダでは、xxf xs = #xs. :: [*] -> numその型はミランダ構文にあると思います。

Haskell のlengthis ですが:: [a] -> Int、ここで定義されているように、 isと 2 つのリテラル and を使用:: (Num n) => [a] -> nしているためです。Num(+)01

視覚化に問題がfoldrある場合は、単純に

foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...))))))
      =      a+(b+(c+(d+(e+(...+(z+ 0)...)))))
      = sum [a, b, c, d, e, ..., z]
于 2012-04-29T17:57:43.087 に答える
8

このステップバイステップを見ていきましょう。

関数はlength明らかにあなたが説明したタイプを持っています。HaskellではNum n => [a] -> n。同等のHaskell関数はlength（Intanyの代わりに使用しますNum n）です。

このswap関数は、呼び出す関数を受け取り、最初の2つの引数を逆にします。署名が正しく得られませんでした。です(a -> b -> c) -> b -> a -> c。同等のHaskell関数はflipです。

関数には、foldr説明したタイプがあります。つまり(a -> b -> b) -> b -> [a] -> b。同等のHaskell関数はfoldrです。

次に、メイン式の各サブ式の意味を見てみましょう。

式swap (:) []は(:)関数を受け取り、その引数を交換します。(:)関数のタイプa -> [a] -> [a]は、なので、swappingを実行すると[a] -> a -> [a];が生成されます。a -> [a]スワップされた関数がに適用されるため、式全体が型になり[]ます。結果の関数は、そのアイテムを指定して1つのアイテムのリストを作成します。

簡単にするために、その部分を関数に抽出してみましょう。

singleton :: a -> [a]
singleton = swap (:) []

さて、次の式は(:) . length . singletonです。(:)関数にはまだタイプがありa -> [a] -> [a]ます; 関数が行うこと(.)は、関数を構成することです。したがって、関数foo :: a -> ...と関数がある場合は、タイプがbar :: b -> aになります。したがって、式のタイプは（を返すことを忘れないでください）であり、式のタイプはです。結果の式が行うことは、ちょっと奇妙です。型の値とリストが与えられると、それは無視し、そのリストの番号を付加します。foo . barb -> ...(:) . lengthNum n => [a] -> [n] -> [n]lengthNum(:) . length . singletonNum => a -> [n] -> [n]aa1

簡単にするために、それから関数を作成しましょう。

constPrependOne :: Num n => a -> [n] -> [n]
constPrependOne = (:) . length . singleton

すでにに精通している必要がありますfoldr。関数を使用してリストを右に折ります。この状況ではconstPrependOne、各要素を呼び出すため、式foldr constPrependOne []は入力リストと同じ長さの要素のリストを作成するだけです。それで、それから関数を作りましょう：

listOfOnesWithSameLength :: Num n => [a] -> [n]
listOfOnesWithSameLength = foldr constPrependOne []

リストがある場合は、適用時に[2, 4, 7, 2, 5]取得します。[1, 1, 1, 1, 1]listOfOnesWithSameLength

次に、foldr (+) 0関数は別の右折りです。sumHaskellの関数と同等です。リストの要素を合計します。

それでは、関数を作成しましょう。

sum :: Num n => [n] -> n
sum = foldr (+) 0

ここで関数を作成する場合：

func = sum . listOfOnesWithSameLength

...結果の式を取得します。いくつかのリストが与えられると、1つだけで構成される同じ長さのリストを作成し、そのリストの要素を合計します。lengthつまり、はるかに遅いアルゴリズムを使用するだけで、とまったく同じように動作します。したがって、最終的な関数は次のとおりです。

inefficientLength :: Num n => [a] -> n
inefficientLength = sum . listOfOnesWithSameLength
于 2012-04-29T17:06:41.137 に答える