一种基于邻接对构建图邻接列表的方法，类似于 MIT 方案中的“fold”

问题描述 投票：0回答：1

最近自学MIT 6.5151课程时，先看了CS 61AS Unit 0作为准备。然后我按照ps0的要求阅读了SICP 1到2.1（以及相关的讲义）（也按照CS 61A笔记的要求阅读了2.2.1），然后软件灵活性设计（SDF）序言，第1章和部分内容方案附录。

目前我正在阅读 SDF 第 2 章并做练习 2.11 (f)。

f。另一个重要的扩展是构建 make-converter，以便它 可以根据需要从之前导出复合转换 注册的转换。这将需要图形搜索。

我想让由 

unit-conversion-key-graph
构造的 
unit-conversion-pairs
等于以下代码中的 
((tonne (kg g)) (celsius (kelvin fahrenheit)))
。

但是在 

set-car!
中使用 
fold
会抛出错误，因为 
res
可能像 fold 中的 
state
变量一样使用（这与 python 中的 
for i in range(10): i=i+1; print(i)
类似，但后者不会抛出错误并且 
 i=i+1
根本不执行任何操作。）。这是一项限制。它将抛出错误“;作为第一个参数传递给 car 的对象#!unspecified，不是正确的类型。” 
set-car!
之后的某个时间。

以下

unit-conversion-list
是为了与代码库中的此代码块保持一致，其中每个单元对都与一些转换过程配对。

(define (displayln x)
      (newline)
      (display x))

(define unit-conversion-list '(((celsius . kelvin) . 1) ((tonne . kg) . 2)
                                ((tonne . g) . 3) ((celsius . fahrenheit) . 4)))
(define unit-conversion-pairs (map car unit-conversion-list))
(displayln unit-conversion-pairs)
; display:
; ((celsius . kelvin) (tonne . kg) (tonne . g) (celsius . fahrenheit))

;; https://stackoverflow.com/a/7382392/21294350
(define (list-set! lst k val)
    (if (zero? k)
        (begin
          (displayln "set to")
          (displayln val)
          (set-car! lst val))
        (list-set! (cdr lst) (- k 1) val)))

;; https://cookbook.scheme.org/find-index-of-element-in-list/
(define (list-index fn lst)
  (displayln lst)
  (let iter ((lst lst) (index 0))
    (if (null? lst)
        -1
        (let ((item (car lst)))
          (if (fn item)
              index
              (iter (cdr lst) (+ index 1)))))))

(define (adjacency-pairs-to-adjacency-list adjacency-pairs)
  (fold 
    (lambda (adjacency-pair res) 
      (let* ((from (car adjacency-pair))
            (to (cdr adjacency-pair))
            (from-idx 
              (list-index 
                (lambda (adjacent-list-elem) (equal? from (car adjacent-list-elem))) 
                res)))
        (if (>= from-idx 0)
          (begin 
            (displayln from-idx) 
            (list-set! res from-idx (list from (list (cadr (list-ref res from-idx)) to)))
            (displayln res)
            (displayln "ending"))
          (cons (list from to) res))))
    '()
    adjacency-pairs))

(define unit-conversion-key-graph (adjacency-pairs-to-adjacency-list unit-conversion-pairs))
(displayln unit-conversion-key-graph)

我们可以定义一个迭代函数来解决上述问题，其基本思想相同：

(define (adjacency-pairs-to-adjacency-list adjacency-pairs)
  (let iter ((rest-adjacency-pairs adjacency-pairs)
              (res '()))
    (if (null? rest-adjacency-pairs)
      res
      (let* ((adjacency-pair (car rest-adjacency-pairs)))
        (let* ((from (car adjacency-pair))
              (to (cdr adjacency-pair))
              (from-idx 
                (list-index 
                  (lambda (adjacent-list-elem) (equal? from (car adjacent-list-elem))) 
                  res)))
          (let ((rest-adjacency-pairs (cdr rest-adjacency-pairs)))
            (if (>= from-idx 0)
              (begin 
                (displayln from-idx) 
                (list-set! res from-idx (list from (list (cadr (list-ref res from-idx)) to)))
                (displayln res)
                (displayln "ending")
                (iter rest-adjacency-pairs res))
              (iter rest-adjacency-pairs (cons (list from to) res))))))))
)

那么有没有一些类似于上面

fold
（两本书都推荐函数式编程）但没有上述限制的内部MIT计划函数可以使
unit-conversion-key-graph
正确？

graph scheme fold mit-scheme
1个回答
0
投票

我想让由 

unit-conversion-key-graph
构造的 
unit-conversion-pairs
等于以下代码中的 
((tonne (kg g)) (celsius (kelvin fahrenheit)))
。

（以函数式而非命令式的方式）。

功能代码的一个重要部分是不可变数据结构——添加、删除或更改元素会返回一个包含更改的新结构（可能与原始结构共享结构以节省内存）。没有任何标准函数可以以这种方式更新列表，但很容易编写一个函数并将其与折叠原始对列表相结合：


;;; returns a new alist with the value of the element keyed with `key` replaced
;;; with the result of calling `f` on that value. If not present, adds a new
;;; mapping with a value created by calling `f` on `(default-thunk)`
;;; Uses `eq?` to ompare keys
(define (alistq-update alist key f default-thunk)
  (cond
   ((null? alist)
    (list (cons key (f (default-thunk)))))
   ((eq? key (caar alist))
    (cons (cons key (f (cdar alist))) (cdr alist)))
   (else
    (cons (car alist) (alistq-update (cdr alist) key f default-thunk)))))

;;; Like alistq-update, but takes a default value instead of a procedure to
;;; call.
(define (alistq-update/default alist key f default-value)
  (alistq-update alist key f (lambda () default-value)))

(define (adjacency-pairs->lists pairs)
  (fold
   (lambda (p alist)
     (alistq-update/default alist (car p) (lambda (list) (cons (cdr p) list)) '()))
   '() pairs))

;; ((celsius fahrenheit kelvin) (tonne g kg))
(displayln (adjacency-pairs->lists unit-conversion-pairs))

注意这会产生 

((celsius fahrenheit kelvin) (tonne g kg))
而不是 
((tonne (kg g)) (celsius (kelvin fahrenheit)))
；在关联列表中顺序并不重要，并且删除额外的嵌套列表将使以后访问值变得更简单。如果第二种形式是你真正想要的，你可以做

(map (lambda (p) (list (car p) (cdr p))) '((celsius fahrenheit kelvin) (tonne g kg)))

得到它。

关联列表虽然有用且易于使用，但它是一种 O(N) 数据结构 - 随着存储在其中的事物数量的增加，使用它们进行操作的时间会以线性方式增加。列表越大，程序越慢。麻省理工学院计划附带许多不同的键值映射数据结构，其中包括一种具有高效不可变操作的权重平衡树。让我们尝试一下：


;;; No idea why these aren't provided by MIT Scheme already
(define (wt-tree->alist wt-tree)
  (wt-tree/fold (lambda (key value list) (cons (cons key value) list))
                '()
                wt-tree))

(define (wt-tree/update wt-tree key f default)
  (let ((current (wt-tree/lookup wt-tree key default)))
    (wt-tree/add wt-tree key (f current))))

(define symbol-wt-tree-type (make-wt-tree-type symbol<?))

(define (adjacency-pairs->wt-tree pairs)
  (fold
   (lambda (p wt-tree)
     (wt-tree/update wt-tree (car p) (lambda (list) (cons (cdr p) list)) '()))
   (make-wt-tree symbol-wt-tree-type)
   pairs))

(displayln (wt-tree->alist (adjacency-pairs->wt-tree unit-conversion-pairs)))
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.