【Scheme】编程学习 (二) —— 基础

简介: Scheme 编程语言学习第二节基础

本文章可以跟视频课程一起看,做了一些补充说明

原视频地址:


I - 概述


本节主要介绍 Scheme 的基础,包含以下四个部分:

  • 两种数据结构点对 (Pairs) 和 表 (Lists),以及如何创建
  • Loops
  • 两种特殊的过程 (Procedures) Map 与 Fold
  • 注意

Scheme 是一种函数式编程语言,什么意思呢?就是说它的参数可以为函数,返回值为函数,而且必须有返回值,若没有返回值,则接连的函数式无法继续执行下去。前一个函数的结果为后一个函数的参数。

而且 Scheme 是一种脚本语言,也就是类似 Python 需要解释器。不同于编译语言和伪编译语言。

II - 数据结构

2.1 - 点对 Pairs


(cons 1 2)

上述代码是调用过程 (Procedure) 的方式,( + 过程名称 + 参数 + ) , 过程与函数类似,调用过程可以理解为调用函数,这里过程名为 cons 用于创建点对,此调用结果为:

(1 . 2)

也可以使用嵌套的过程

(cons (cons 1 2) 3)
; ((1 . 2) . 3)

定义符号 (Symbol),使用 define 过程,定义符号 foo 为点对 (1 . 2)

(define foo (cons 1 2))
foo
; 检查 foo 输出 (1 . 2)

点对包含两个域 carcdr

有两个同名的过程:
car 获取数据对象中的第一个元素
cdr 获取数据对象中的第二个元素

(car foo)
; 1
(cdr foo)
; 2

符号 foo 中第一个元素为 1 ,foo 中第二个元素为 2,car / cdr 过程不一定获取的是数据对象中的单个元素,也可以是复合的结构。

2.2 - 表 Lists

2.2.1 - 单元素表和空表


我们使用前一小节点对中的 cons 过程,构建一个特殊的点对,它的两个域,一个为 1 ,另一个为 null 也就是空,得到只有一个元素的点对,也是只包含一个元素的表。

(cons 1 null)
; (1)

定义 bar 符号为只有一个元素的点对,对其进行 car, cdr 操作

(define bar (cons 1 null))
bar
; 检测 bar 得到结果 (1)

(car bar)
; 1
(cdr bar)
; ()

空的括号 () 是另一种表示 null 的形式,也是一个不包含任何元素的表。也就是说任何一个表最后一个元素都为 null 。

当我们对解释器输入这个特殊的符号 null 时,我们同样得到 空表

null
; ()

2.2.2 - 复合操作

(cons 1 (cons 2 null))
; (1 2)

创建一个包含 2 和 null 的点对,接着创建一个点对元素为 1 和刚刚创建的点对。获得一个点对 (1 2),但解释器表示为包含元素为 1 和 2 的表,也就是说表结构为很多点对的集合。

(cons 1 (cons 2 (cons 3 null)))
; (1 2 3)

使用 (cons 2 (cons 3 null)) 可以获得一个包含 2 和 3 的表,使用结果作为右域与元素 1 创建点对,得到 一个包含元素为 1 2 3 的表。

定义一个符号 mylist 为包含元素 1 2 3 的表

(define mylist (cons 1 (cons 2 (cons 3 null))))

mylist
;(1 2 3)

(car mylist)
;1

(cdr mylist)
;(2 3)

对 mylist 应用 car 得到此表的第一个元素
对 mylist 应用 cdr 则得到所有剩下的元素

(cadr mylist)
; 2

cadr 表示首先进行 cdr ,然后进行 car

(car (cdr mylist))

cdr mylist 得到子表 (sublist) :(2 3)
接着 对此子表应用 car,也就是获取此子表的第一个元素,即 2

同样的

(caddr mylist)
; 结果为 3

cdr mylist 为 (2 3) ,对结果再次 cdr 为 3,car 此结果即为 3

速记:复合的左右域操作,顺序为从右向左。

2.2.3 - list 过程

我们也可以使用前一篇文章中见到的 list 过程来创建表。

(equal? (list 1 2 3) mylist)

过程 list 用于构建表,equal? 用于比较两个元素内容是否相等,比较使用 list 过程构建的表和使用 cons 构建的表是否相同,得到结果

#t

在 Scheme 中布尔值有两个 #t 和 #f , #t 表示 true, #f 表示 false

注意跟 C 语言或其他编程语言不一样的是
if (0)if (#f) 不等价 if (0) 会进入 if 分支,if (#f) 则不会,

(list-ref lst n)

list-ref 是一个用于获取表中第 n 个元素的过程

(list-ref (list "a" "b" "c") 1)
; "b"
(list-ref (list "a" "b" "c") 2)
; "c"

list-ref 过程有两个参数,第一个参数为表,第二个参数为表中的第 n 个元素,与 C 语言相同,计数从 0 开始,当计数为 1 时,获取表中第二个元素,即 "b" , 当计数为 2 时,则获取表中第三个元素,也就是 "c"

III - Loops

如何简略地实现 list-ref 过程?

(define (my-list-ref lst n)
    (if (zero? n) ; 如果 n 为 0 
        (car lst) ; 返回 lst 的第一个元素
        (my-list-ref (cdr lst) (- n 1))))
        ; 否则进行递归操作,获取 lst 除第一个意外子表的第 n-1 个元素 

(my-list-ref (list "a" "b" "c") 1)
; "b"
(my-list-ref (list "a" "b" "c") 2)
; "c"

调用实现方式比较粗糙的 my-list-ref 过程,在参数相同时,得到相同的运行结果

此种实现方式被称为 "Loops" ,在其他的编程语言中称为 loop(循环)或 recursion(递归)

IV - 两种特殊的过程

4.1 - Map

(map procedure lst)
map 过程对参数表 lst 中的每一个元素应用过程 procedure 。

; 定义一个符号 baz 内容为包含 1 2 3 三个元素的表
(define baz (list 1 2 3))
; 定义一个过程 double ,结果为入参乘以 2
(define (double x) (* x 2))

(map double baz)
; (2 4 6)

对表 (1 2 3) 中的每一个元素应用 double 过程得到结果 (2 4 6)

; 定义一个过程 double-all 
(define (double-all x) (map double x))

(double-all baz)
; (2 4 6)

这次只需要调用一个过程就可以得到相同的结果。

那么我们如何简略地实现 map 过程呢?

(define (my-map fn lst)
    (if (null? lst)
        null
        (cons (fn (car lst)) (my-map fn (cdr lst)))))

(my-map double baz)
; (2 4 6)

my-map 的实现也是通过构建递归,首先如果为空则返回空,

if (null? lst)
    null

判断是否为空 返回 null ,这里这里不仅是特殊情况处理,也是递归结束条件,如果处理到最后一个元素 (根据本文前面的内容,list 的最后一个元素为 null),则返回 null 结束

不为空 就会创建一个点对,此处应用到了 2.2 节中可以使用 cons 过程创建 list (表) 的内容

(cons (fn (car lst)) (my-map fn (cdr lst)))

生成表第一个元素为对表的第一个元素应用 fn ,(cdr lst) 获取除了第一个元素外,lst 中剩余的所有元素 因此,生成表的第二个元素也会获取原表第二个元素,并对此元素应用 fn ,依次类推。即对表中的所有元素都应用了 fn 。

4.2 - Fold

(define qux (list 1 2 3 4))
; 定义符号 qux 内容为 (1 2 3 4) 的表

(foldr + 0 qux)
; 结果为 10

调用 foldr 过程有三个入参, + 0 qux,0 为起始元素,然后将 0 与 qux 中的元素从后向前依次累加,即:

0 + 4
4 + 3
7 + 2
9 + 1

结果为 10

foldr 表示 fold up 堆叠,从最后一个元素开始一个一个叠起来。
有一些类似 C++ 标准库的 std::accumulate 函数,累加 需要指定初始值,因此

; 指定初始值为 2000
(foldr + 2000 qux)
; 结果为 2010

foldr 不仅可以指定累加 还可以指定其他过程,如

(foldr * 1 qux)
; 结果为 24

计算过程为:

1 * 4
4 * 3
12 * 2
24 * 1

结果为 24

同理

(foldr * 0 qux)
; 0

对于 map 同样的操作,我们如何实现 foldr

(define (my-foldr fn start lst)
    (if (null? lst)
        start
        (fn (car lst) (my-foldr fn start (cdr lst)))))

(my-foldr + 0 qux)
; 10
(my-foldr * 1 qux)
; 24

首先判断是否为 null 与 my-map 一样,既是特殊情况处理,又是结束条件,返回 start

(fn (car lst) (my-foldr fn start (cdr lst)))

其他情况返回 计算 fn (第一个元素,剩余元素 与 start 元素fn 的结果) 。剩余元素仍然是 lst 则 返回 第二个元素与剩余元素 加 start 元素 fn 的结果...

以此类推,递归到最后一个元素时,则计算 最后一个元素 与 start 元素 fn 的结果。并返回上层调用,计算倒数第二个元素与这个结果的 fn 的值,然后返回更上一层调用...

举例 如果 lst 表中有两个元素 (1 2) , fn 为 +

则递归过程展开

(+ 1 (my-foldr + start (cdr lst)))
; 再展开
(+ 1 (+ 2 start))
; 即 start + 2 + 1

V - 注意事项

mzscheme 称空为 null ,其实是 nil

(define nil null)
目录
相关文章
|
人工智能 算法 Java
【Scheme】编程学习(一) —— 概述
Scheme 是一种编程语言,为 Lisp 的一种变体,本文概述 Scheme 语言
448 0
|
SQL 分布式计算 资源调度
Apache Doris 整合 FLINK CDC + Iceberg 构建实时湖仓一体的联邦查询
这篇教程将展示如何使用 Flink CDC + Iceberg + Doris 构建实时湖仓一体的联邦查询分析,Doris 1.1版本提供了Iceberg的支持,本文主要展示Doris和Iceberg怎么使用,同时本教程整个环境是都基于伪分布式环境搭建,大家按照步骤可以一步步完成。完整体验整个搭建操作的过程。
2990 1
|
数据可视化 关系型数据库 MySQL
Apache Superset 1.2.0教程 (三)—— 图表功能详解
通过之前章节的学习,我们已经成功地安装了superset,并且连接mysql数据库,可视化了王者英雄的数据。使用的是最简单Table类型的图表,但是superset还支持非常多的图表类型。 本文我们将对各种图表类型进行逐一的演示,文章较长。
1210 0
Apache Superset 1.2.0教程 (三)—— 图表功能详解
|
存储 C++
【Scheme】编程学习 (三) —— 闭包
本节主要讲述 Scheme 中闭包概念及使用
202 1
|
C语言 C++
【Scheme】编程学习 (四) —— 递归
Scheme 编程通常的使用方法为递归
185 0
|
分布式计算 调度 Spark
Spark作业调度中stage的划分
Spark在接收到提交的作业后,会进行RDD依赖分析并划分成多个stage,以stage为单位生成taskset并提交调度。
Spark作业调度中stage的划分
|
人工智能 达摩院 算法
浅谈面向专业用户的工具设计:达摩院 AI Earth 地球科学云平台设计案例
作者: 达摩院设计-壳恪你了解我们的地球嘛?从眼前方寸到浩瀚星空,你是否从卫星视角看过我们的家园?随着对地观测技术的发展和数智时代的到来,我们不仅仅满足于看见地球,更想要看懂地球。原本科研工作者们需要通过ArcGIS、Envi等传统桌面软件对本地存储的卫星遥感影像进行分析处理,从而得出地球上的自然资源如何分布、我们的城市在数十年间发生了什么样的变化、生态环境的变迁会对人类造成什么样的影响,而达摩院
775 2
浅谈面向专业用户的工具设计:达摩院 AI Earth 地球科学云平台设计案例
|
安全 Java 数据安全/隐私保护
【SpringBoot 基础系列】SpEL 语法扫盲与查询手册
Spring 表达式语言简称为 SpEL,一种类似 Ognl 的对象图导航语言(对于 ognl 不熟悉的同学可以参考一下: Ognl 系列博文) SeEL 为 Spring 提供了丰富的想象空间,除了一些基本的表达式操作之外,还支持
683 0
【SpringBoot 基础系列】SpEL 语法扫盲与查询手册
|
存储 运维 Cloud Native
PolarDB-X 与 X-DB、PolarDB
PolarDB-X与X-DB、PolarDB都是阿里巴巴的数据库产品。那么他们之间有什么样的关系?
PolarDB-X 与 X-DB、PolarDB
|
域名解析 缓存 监控
网络TCP/IP基础(OSI七层网络参考模型、协议及原理)
网络分层、七层参考模型功能介绍、TCP/IP五层模型常见协议、网络层协议介绍、ICMP、IGMP、IP、ARP、RARP、传输层协议介绍、TCP、建立TCP连接的三次握手原理、为什么要三次握手、四次断开原理、握手是三次,为什么断开要四次、什么是TCP半关闭状态、UDP、应用层协议介绍、HTTP、FTP、TFTP、SMTP、SNMP、DNS、五层模型常见设备
1001 1