Oz - 一般的計算モデル(宣言的プログラミング技法(リストの平坦化の計算量))

コンピュータプログラミングの概念・技法・モデル
(IT Architect' Archive
クラシックモダン・コンピューティング6)
(IT Architects’Archive CLASSIC MODER)
(翔泳社)
セイフ・ハリディ (著), ピーター・ヴァン・ロイ (著)
Peter Van-Roy (著), Seif Haridi (著), 羽永 洋 (翻訳)
原書: Concepts, Techniques,
and Models of Computer Programming

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• Oz (プログラミング言語)
• Mozartプログラミングシステム(Mozart 2) (実装)

コンピュータプログラミングの概念・技法・モデル(IT Architect' Archiveクラシックモダン・コンピューティング6) (IT Architects’Archive CLASSIC MODER)(セイフ・ハリディ (著)、ピーター・ヴァン・ロイ (著)、Peter Van-Roy (著)、 Seif Haridi (著)、羽永 洋　(翻訳) 、翔泳社、原書: Concepts, Techniques, and Models of Computer Programming(CTM))の第部(一般的計算モデル)、第3章(宣言的プログラミング技法)、3.10(練習問題)、12.(リストの平坦化の計算量)を解いてみる。

12.(リストの平坦化の計算量)

1つ目。

{Flatten [[a b] [[c] [d]] nil [e [f]]]}
{Append {Flatten [a b]}
        {Flatten [[[c] [d]] nil [e [f]]]}}
{Append a|{Flatten [b]}
        {Append {Flatten [[c] [d]]}
                {Flatten [nil [e [f]]]}}}
{Append a|b|{Flatten nil}
        {Append {Append {Flatten [c]}
                        {Flatten [[d]]}}
                {Append {Flatten nil}
                        {Flatten [[e [f]]]}}}}
{Append [a b]
        {Append {Append c|{Flatten nil}
                        {Append {Flatten [d]}
                                {Flatten nil}}}
                {Append nil
                        {Append {Flatten [e [f]]}
                                {Flatten nil}}}}}
{Append [a b]
        {Append {Append [c]
                        {Append d|{Flatten nil}
                                nil}}
                {Append nil
                        {Append e|{Flatten [f]}
                                nil}}}}
{Append [a b]
        {Append {Append [c]
                        [d]}
                {Append nil
                        {Append e|f|{Flatten nil}
                                nil}}}}
{Append [a b]
        {Append {Append [c]
                        [d]}
                {Append nil
                        {Append e|f|nil}
                                nil}}}}
{Append [a b]
        {Append [c d]
                {Append nil
                        {Append [e f]
                                nil}}}}
{Append [a b]
        {Append [c d]
                {Append nil
                        [e f]}}}
{Append [a b]
        {Append [c d]
                [e f]}}
{Append [a b]
        [c d e f]}
[a b c d e f]

2つ目。

{Flatten [[a b] [[c] [d]] nil [e [f]]]}
{FlattenD [[a b] [[c] [d]] nil [e [f]]]
          nil}
{FlattenD [a b]
          {FlattenD [[[c] [d]] nil [e [f]]]
                    nil}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {Flatten [nil [e [f]]]
                             nil}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              {FlattenD [[e [f]]]
                                        nil}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              {FlattenD [e [f]]
                                        {FlattenD nil
                                                  nil}}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              {FlattenD [e [f]]
                                        nil}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              e|{FlattenD [[f]]
                                          nil}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              e|{FlattenD [f]
                                         {FlattenD nil nil}}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              e|{FlattenD [f]
                                          nil}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              e|f|{Flatten nil nil}}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    {FlattenD nil
                              e|f|nil}}}
{FlattenD [a b]
          {FlattenD [[c] [d]]
                    [e f]}}
{FlattenD [a b]
          {FlattenD [c]
                   {FlattenD [[d]]
                             [e f]}}}
{FlattenD [a b]
          {FlattenD [c]
                    {FlattenD [d]
                              {Flatten nil
                                       [e f]}}}}
{FlattenD [a b]
          {FlattenD [c]
                    {FlattenD [d]
                              [e f]}}}
{FlattenD [a b]
          {FlattenD [c]
                    d|{Flatten nil [e f]}}}
{FlattenD [a b]
          {FlattenD [c]
                    d|[e f]}}
{FlattenD [a b]
          {FlattenD [c]
                    [d e f]}}
{FlattenD [a b]
          c|{FlattenD nil [d e f]}}
{FlattenD [a b]
          c|[d e f]}
{FlattenD [a b]
          [c d e f]}
a|{Flatten [b]
           [c d e f]}
a|b|{Flatten nil
             [c d e f]}
a|b|[c d e f]
[a b c d e f]