《函數(shù)式程序設(shè)計語言.ppt》由會員分享，可在線閱讀，更多相關(guān)《函數(shù)式程序設(shè)計語言.ppt（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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