ハスケル/ミランダ：関数のタイプを探す

Question

概要：これは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のに間違ってそれを翻訳したくありませんでした。基本的に、一方の変数に*型があり、他方の型に*がある場合は、どちらの型でも構いませんが、どちらも同じ型でなければなりません。 **を持っている場合は、*と同じ型を持つ必要はありません。私はそれがiskell usuageのa、b、cなどに相当すると思います。あなたは、この定義から

length :: [*] -> num. 

を与えるので、それは私がスワップにかかると思うもののリストの長さを見つけることが確認でき、これまで

長の定義から作業

マイ関数と2つのパラメータを入れ替え、2つのパラメータを入れ替えた関数を作ります。これにより、

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

foldrは、バイナリ関数（プラスのような）で開始値とリストを取り、その関数を使用してリストを右から左へフォールドします。これは

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

私は関数合成で、最初のドット（。）の右側にある例のすべてのためにそれが最初foldrの引数として与えられますので、リストを生成する必要があるので、右結合である知っています。

foldr関数は単一の値（リストを折りたたんだ結果）を出力するので、戻り値の型はある種のpolytypeになり、polytypeのリストにはなりません。

私の問題

私は本当にここから行くためにどこか不明です。私は、スワップが別の議論をとる必要があることを見ることができます。この部分的な適用は、すべてが機能であることを暗示しますか？私はかなり混乱しています！

Answer 1

あなたはすでに答えを持っている

それはすべてを一度に見ることは簡単ですので、私はちょうどステップによって導出ステップを書き留めます：だから

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です。私はそのタイプがMiranda構文の:: [*] -> numだと思います。

Haskellのlengthが:: [a] -> Intであるが、ここで定義されるように、それはNumの(+)と2リテラル、0と1を使用していますので、それは:: (Num n) => [a] -> nです。

トラブルfoldrを可視化がある場合は、それだけで[Haskellのプラットフォーム]（http://hackage.haskell.org/platform/）をインストールし、それをテストするためにGHCiのを使うだけで

foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...)))))) 
      == a+(b+(c+(d+(e+(...+(z+ 0)...))))) 
      == sum [a,b,c,d,e,...,z] 

Answer 2

このステップバイステップを行ってみましょう。

length関数は、明らかにあなたが記述した型です。ハスケルではNum n => [a] -> nです。同等のHaskell関数はlengthです（Num nの代わりにIntを使用します）。

swap関数は、最初の2つの引数を呼び出して元に戻す関数を取ります。あなたは署名を正当なものにしませんでした。それは(a -> b -> c) -> b -> a -> cです。同等のHaskell関数はflipです。

foldr関数には、記述した型があります。すなわち(a -> b -> b) -> b -> [a] -> bです。同等のHaskell関数はfoldrです。

ここで、メイン表現の各サブ式が意味するものを見てみましょう。

式swap (:) []は、(:)関数を引数に取り替えます。 (:)関数の型がa -> [a] -> [a]なので、swap pingを実行すると、[a] -> a -> [a]となります。スワップされた関数が[]に適用されるため、式全体の型はa -> [a]となります。結果として得られる関数は、そのアイテムが与えられた1つのアイテムのリストを作成することを行います。

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

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

は今、次の式が(:) . length . singletonです。 (:)関数のタイプは、まだa -> [a] -> [a]です。 (.)の機能は機能を構成しているため、機能がfoo :: a -> ...で機能がbar :: b -> aの場合、foo . barのタイプはb -> ...となります。式(:) . lengthはタイプNum n => [a] -> [n] -> [n]です（lengthはNumを返します）。(:) . length . singletonの式はNum => a -> [n] -> [n]です。どのような結果表現が奇妙なのですか：タイプaといくつかのリストの任意の値を与えられた場合、それはaを無視し、そのリストに番号1を付加します。

簡単にするために、のは、その外の機能を作成してみましょう：

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]を持っている場合はlistOfOnesWithSameLengthを適用するとき、あなたは[1, 1, 1, 1, 1]を取得します。

次に、foldr (+) 0の機能はもう1つ右に折りたたまれています。 Haskellのsum関数と同等です。リストの要素を合計します。

それでは、機能を作ってみましょう：

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

あなたは今の機能を構成する場合：

func = sum . listOfOnesWithSameLength 

...あなたは結果の式を得ます。いくつかのリストがあれば、それは等しい長さのリストを作成し、そのリストの要素を合計します。言い換えれば、正確にはlengthのように振る舞いますが、アルゴリズムはずっと遅いだけです。だから、最後の機能は次のとおりです。

inefficientLength :: Num n => [a] -> n 
inefficientLength = sum . listOfOnesWithSameLength