函數(shù)式程序設計語言.ppt

2020年1月26日星期日 程序設計語言范型ProgrammingLanguagesParadigms 教師 張榮華計算機科學與技術學院華北電力大學 函數(shù)式程序設計語言 Scheme語言數(shù)據(jù)抽象 第二部分 第五章 Scheme語言數(shù)據(jù)抽象 第五章 3 回顧 任何強有力的程序設計語言都必須能表述基本的數(shù)據(jù)和過程 還需要提供對數(shù)據(jù)和過程進行組合和抽象的方法 摘自 計算機程序的構造和解釋 控制抽象 表達式層次 語句層次 程序單元層次 數(shù)據(jù)抽象 本章研究內(nèi)容 Scheme語言數(shù)據(jù)抽象 第五章 4 回顧 Scheme語言控制抽象 第五章第二部分 將一個過程的使用方式 與該過程究竟如何通過更基本的過程實現(xiàn)的具體細節(jié)相互分離的一種技術 基本數(shù)據(jù) 數(shù) 基本過程 算數(shù)運算 用復合 條件 參數(shù)將過程組合起來形成復合過程 通過define lambda做過程抽象 過程的計算模式 遞歸計算和迭代計算過程 高階過程Scheme語言數(shù)據(jù)抽象 第五章第三部分 討論程序設計語言提供的將數(shù)據(jù)對象組合起來形成復合數(shù)據(jù)的方式 Scheme語言數(shù)據(jù)抽象 第五章 5 內(nèi)容 1 數(shù)據(jù)抽象導引1 1序?qū)? 2有理數(shù)包的抽象屏障2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 Scheme語言數(shù)據(jù)抽象 第五章 6 1 數(shù)據(jù)抽象導引 數(shù)據(jù)抽象將程序中處理數(shù)據(jù)對象的表示的部分 與處理數(shù)據(jù)對象的使用的部分相互隔離起來的一種技術 例如 考慮線性組合 ax by define linear combinationabxy ax by define linear combinationabxy add mulax mulby 數(shù)據(jù)抽象的關鍵 構造函數(shù) 粘合劑 選擇函數(shù) 分離劑 Scheme語言數(shù)據(jù)抽象 第五章 7 實例 有理數(shù)的算術運算 假定 存在一種方法可以從分子和分母構造出有理數(shù) 存在一種方法可以從已經(jīng)存在的有理數(shù)中分離它的分子和分母 make rat numer denom 從分子n和分母d構造有理數(shù)并返回 返回有理數(shù)x的分母 返回有理數(shù)x的分子 構造函數(shù) 選擇函數(shù) Scheme語言數(shù)據(jù)抽象 第五章 8 實例 有理數(shù)的算術運算 例如 實現(xiàn)兩個有理數(shù)相加 Scheme語言數(shù)據(jù)抽象 第五章 9 內(nèi)容 1 數(shù)據(jù)抽象導引1 1序?qū)? 2有理數(shù)包的抽象屏障2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 Scheme語言數(shù)據(jù)抽象 第五章 10 1 1序?qū)?Scheme語言提供的構造函數(shù)和選擇函數(shù) 內(nèi)部的基本過程 cons模擬構造函數(shù)的功能 構造序?qū)?表結構 由序?qū)嬙炱饋淼膹秃蠑?shù)據(jù)對象 內(nèi)部基本過程 car和cdr模擬選擇函數(shù)的功能 實現(xiàn)對序?qū)Φ牟僮?Scheme語言數(shù)據(jù)抽象 第五章 11 內(nèi)容 1 數(shù)據(jù)抽象導引1 1序?qū)? 2有理數(shù)包的抽象屏障2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 Scheme語言數(shù)據(jù)抽象 第五章 12 1 2有理數(shù)包的抽象屏障 使用有理數(shù)的程序 add rat sub rat make rat numer denom 抽象 抽象 1 2 Scheme語言數(shù)據(jù)抽象 第五章 13 內(nèi)容 1 數(shù)據(jù)抽象導引2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 Scheme語言數(shù)據(jù)抽象 第五章 14 2 1序列與閉包性質(zhì) 序?qū)Φ?盒子和指針表示方式 例如 每個對象表示一個指向盒子的指針左邊的方盒放著序?qū)Φ腸ar右邊的方盒放著序?qū)Φ腸drcons的閉包性質(zhì)建立元素本身也是序?qū)Φ男驅(qū)?表結構 Scheme語言數(shù)據(jù)抽象 第五章 15 2 1序列與閉包性質(zhì) 序列 Sequences 表 list 由序?qū)嬙斐龅囊环N數(shù)據(jù)結構 表示一批數(shù)據(jù)對象的有序集合 Scheme語言數(shù)據(jù)抽象 第五章 16 內(nèi)容 1 數(shù)據(jù)抽象導引2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 Scheme語言數(shù)據(jù)抽象 第五章 17 2 2表操作 例1 Scheme語言數(shù)據(jù)抽象 第五章 18 2 2表操作 例2 用迭代計算模型改寫下面的過程 Scheme語言數(shù)據(jù)抽象 第五章 19 2 2表操作 例3 實現(xiàn)兩個表的合并 Scheme語言數(shù)據(jù)抽象 第五章 20 內(nèi)容 1 數(shù)據(jù)抽象導引2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 Scheme語言數(shù)據(jù)抽象 第五章 21 2 3表映射 表映射將某種變換應用于一個表的所有元素 得到的結果構成新的表 例如 將一個表中的元素按給定因子縮放 Scheme語言數(shù)據(jù)抽象 第五章 22 2 3表映射 問題 如何將表的映射這個一般性問題進行抽象 解決方法 將其中的公共模式表述為一個高階過程map 研究Scheme標準提供的內(nèi)部map過程 Scheme語言數(shù)據(jù)抽象 第五章 23 2 3表映射 問題 如何將表的映射這個一般性問題進行抽象 解決方法 將其中的公共模式表述為一個高階過程map 研究Scheme標準提供的內(nèi)部map過程 Scheme語言數(shù)據(jù)抽象 第五章 24 使用map改進scale list Scheme語言數(shù)據(jù)抽象 第五章 25 內(nèi)容 1 數(shù)據(jù)抽象導引2 表結構2 1序列與閉包性質(zhì)2 2表操作2 3表映射3 函數(shù)式語言高級抽象綜合實例 實例1 對于一棵樹 計算值為奇數(shù)的葉子的平方和 實例2 構造所有為偶數(shù)的斐波那契數(shù)Fib k 的一個表 其中的k小于等于某個給定的整數(shù)n 實例1分析 枚舉一棵樹的樹葉 過濾它們 選出其中的奇數(shù) 對選出的每一個數(shù)求平方 從0開始 用 累積起得到的結果 Scheme語言數(shù)據(jù)抽象 第五章 28 3函數(shù)式語言高級抽象綜合實例 實例1和實例2的信號流流水線處理模式 enumerate treeleaves filter odd map square accumulate 0 enumerate integers map fib filter even accumulate cons 枚舉從0到n的整數(shù) 對每個整數(shù)計算相應的斐波那契數(shù) 過濾它們選出其中的偶數(shù) 從空表開始用cons累積結果 枚舉一棵樹的樹葉 過濾它們選出其中的奇數(shù) 對選出的每一個數(shù)求平方 從0開始用 累積結果 Scheme語言數(shù)據(jù)抽象 第五章 29 習題 利用Scheme語言使用下面的標準組件構造由前n 1個斐波那契奇數(shù)的平方形成的表 enumeratemapfilteraccumulate