#lang plai 球拍倍增功能

Question

我正在做一个项目，让我们习惯在编程语言课程中使用的plai类型语言。我一直被困在一个真正困扰我的问题上（完成所有其他问题都没有问题）。我们要采用这个数据类型定义：

(define-type Tree
[leaf (val number?)]
[node (val number?)
(left Tree?)
(right Tree? ) ] ) 

然后"实现函数'scaled'，它接受一棵树并返回一棵具有相同形状的树，但所有值都乘以给定的比例。

示例：（缩放（节点 -5（叶

6）（叶 -7））2）应生成（节点 -10（第12页）（叶-14））"

所以基本上我只需要通过给定的值将所有这些值多地排列，在本例中为 2。

以下是我在尝试不同方法后到目前为止所拥有的：

(define (scaled [ t Tree?] [n  number?] )  
(type-case Tree t  
[leaf (val) val] 
[node (val left right) ( * val (scaled left) (scaled right)  n  ) ] ) )    

我

基于我为作业的其他部分创建的先前代码，并且我做对了。问题是，它将所有数字和结果"成功"乘以 420 的解决方案，而不是单独将每个值相加。我知道这与我放置"n"有关，但我尝试了很多不同的方法，但没有运气。如果有人有任何有用的提示/提示/解决方案，将不胜感激。

谢谢！

Answer 1

思考问题的方法不是下降到较低的实现级别，而是上升到我们可以思考scaled是什么的级别。问题不在于弄清楚在哪里放n.它正在弄清楚scaled应该做什么。

无论它做什么，它都需要返回一棵树。

; DefType F1 : Any -> Tree
(define (f1 x)
  (leaf 42))

下一个最重要的事情是它需要将一棵树作为输入。

; DefType F2 : Tree -> Tree
(define (f2 [t Tree?])
  (leaf 42))

接下来必须解决的输入和输出之间存在同构性。输出树的结构需要与输入树的结构相匹配。

; DefType F3 : Tree -> Tree
(define (f3 [t Tree?])
  t)

这为我们提供了我们想要的东西，但从函数式编程的角度来看，这是以牺牲质量为代价的，因为f3返回对输入的引用，而不是从输入派生的值。该函数需要返回与输入值具有相同结构的新输出值。要复制结构，函数必须在传递node时返回node，在传递leaf时返回leaf。

; DefType F4 : Tree -> Tree
(define (f4 [t Tree?])
  (type-case Tree t
    [leaf (val) (leaf val)]
    [node (val left right)
       (node val (f4 left)(f4 right))]))

现在类型已经整理好了，是时候处理将输入树转换为输出树了。这需要向上移动而不是向下移动。开始的地方是重写f4。

; DefType F5 : Tree -> Tree
(define (f5 [t Tree?])
  (type-case Tree t
    [leaf (val) (leaf (id val))]
    [node (val left right)
      (node (id val) (f5 left)(f5 right))]))

重要，但不是很有趣。用任意函数替换id似乎更有趣。如此有趣，可能值得添加第二个参数。

; DefType N2N : Number -> Number
; DefType F6 : Tree (Number -> Number) -> Tree
(define (f6 [t Tree?] [n2n N2N?])
  (type-case Tree t
    [leaf (val) (leaf (n2n val))]
    [node (val left right)
      (node (n2n val) (f6 left) (f6 right))]))

该函数scaled：

; DefType Scaled : Tree Number -> Tree
(let ((f lambda(x y)(* x y)))
  (define (scaled [t Tree?][n Number?])
    (type-case Tree t
      [leaf (val)(leaf (f n val))]
      [node (val left right)
        (node (f n val) (scaled left)(scaled right))])))