Scheme之数据结构和算法

By guenchi at 2018-03-22 • 0人收藏 • 345人看过


从开始玩Scheme来,因为各类库的缺少,手动实现了很多轮子,后来实现服务器Igropyr,又开始造更多轮子。


现在想想,这些轮子的的制造,其实是恶补了自己的数据结构和算法知识,所以现在将这些想法和代码分享出来,希望对一些非计算机专业的人能有帮助。


[本帖会持续更新]


  1. 复合数据结构的实现。

这里的复合数据结构,是指数组,json等Scheme不存在的数据结构,如何用链表实现并进行方便的操作,是使用Scheme遇到的第一个问题。


一开始我将Json模型简化为键值对的组。那么怎么用链表来表达这个结构呢?


通过思考,我发现这个结构可以很方便的满足我的需求:

((key . value) (key . value) ...)

那么怎么通过key访问value的值呢?

通过比较每一个子树的左节点就行了。

(define ref
    (lambda (str x)
        (if (null? str)
            '()
            (if (equal? (caar str) x)
                (cdar str)
                (ref (cdr str) x)))))

那么反过来,通过比较每一个子树的右节点就可以通过value查找key

(define val
    (lambda (str x)
        (if (null? str)
            '()
            (if (equal? (cdar str) x)
                (caar str)
                (val (cdr str) x)))))

或者将这个结构转换为传统的json:


这时,首先需要造一个用字符切割字符串的轮子:

(define str-index
    (lambda (s c)
        (let ((n (string-length s)))
            (let loop ((i 0))
                (cond 
                    ((>= i n) #f)
                    ((char=? (string-ref s i) c) i)
                    (else (loop (+ i 1))))))))

(define split
    (lambda (s c)
        (let loop ((s s))
            (if (string=? s "")
                '()
                (let ((i (str-index s c)))
                    (if i
                        (cons (substring s 0 i) (loop (substring s (+ i 1) (string-length s))))
                        (list s)))))))

下面是json转换代码:

(define list-parser
    (lambda (str)
        (let loop ((str str)(x "{"))
            (if (null? (cdr str))
                (string-append x "\"" (caar str) "\":\"" 
                (if (list? (cdar str))
                    (loop (cdar str) "{")
                    (cdr (car str))) "\"}")
                (loop (cdr str) (string-append x "\"" (caar str) "\":\"" 
                    (if (list? (cdar str))
                        (loop (cdar str) "{")
                        (cdar str)) "\"," ))))))


那么数组呢?


我一开始走了一个大大的弯路。我用一个简单的list来存放数组,有序的组的队列嘛。

想想也没有错啊。


但是这让我的Json结构实现受阻,因为当我将数组放入Json的值时,我的解析器根本没办法判断这是另一个Json键值对还是是一个数组。


这真是一个悲伤的故事:我在努力了几天后,从数学上证明了这个判断是根本不可能的。。。


到现在已经快半年后了,昨天在重读黑客与画家的时候,同时也在读C语言的基本经典著作,这个时候这几本书给了我一个具有深刻启发的观点:


数组其实就是一个键为自然数的hash表!


那么这样以来,我就不用将单链的list插入之前设计的复合双链list。那么我之前遇到的不可能解决的难题,就根本是在给自己找麻烦!


所以数组可以简单的表示为:

((0 . value) (1 . value) (2 . value) ...)

然后通过之前的(ref)过程 可以方便的取得数组内某一项的值。


我们完美的复用了以前所做的所有工作。


这是 @chui 给了我新的思路


他提出可以用向量来作为数组。


好处是向量的ref比较高效,而缺点是长度不可变。


在考虑到尾递归不好保存栈深度的情况下,我放弃用双链表表示数组,转而使用向量。




登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...