1

過去の関数プログラミングの試験問題を解いていて、次の質問があります。

本質的に同じ式を記述する 2 つの方法を次に示します。

f (g(x,y),z,h(t))

f (gxy) z (ht)

(a) 2 つの式の異なる構造を、2 つの異なる種類の木として描いて説明します。

(b) Haskell データ型 Bush a と Tree a を定義して、2 つの異なる構造をキャプチャします。

コースでこのようなことをしたことがないので、ちょっと行き詰まっています。Tree a最初の式は で、2 番目の式は で表す必要があることは後の部分から明らかですがBush a、ここからどこへ行くべきかはよくわかりません。私は次のようなものを推測しました：

data Tree a = Leaf a | Node (Tree a) (Tree a)
data Bush a = Node a [Bush a]

しかし、バイナリ ツリー タイプは使用するのに適しているとは思いません。誰かが私を正しい方向に向けることができますか?

4

1 に答える 1

4

実際には、最初の式は で表されBush、2 番目の式は で表されTreeます。

Haskell では、に適用されることをg x y意味します。C では、が引数のコレクションに適用されることを意味します — . したがって、C では:g xyg(x, y)g{x, y}

f(g(x,y),z,h(t)) = Bush f [Bush g [Bush x [], Bush y []], Bush z [], Bush h [Bush t []]]

  f
  +--g
  |  +--x
  |  +--y
  |
  +--z
  |
  +--h
     +--t

そして Haskell では:

f (g x y) z (h t) = App (App (App f (App (App g x) y)) z) (App h t)

         +
        / \
       /  /\
      +  h  t  
     / \
    /\  z
   f  +
     / \
    /\  y
   g  x
于 2012-11-17T15:45:13.007 に答える