首页 文章

如何在scheme中编写reduce-per-key函数？

提问于
浏览 次
2

“定义一个过程'reduce-per-key'，一个过程reducef和一个关联列表，其中每个键与一个列表配对 . 输出是一个相同结构的列表，除了每个键现在与结果相关联将reducef应用于其关联列表“

我已经写过'map-per-key'和'group-by-key'：

(define (map-per-key mapf lls)
  (cond
    [(null? lls) '()]
    [else (append (mapf (car lls))(map-per-key mapf (cdr lls)))]))

(define (addval kv lls)
  (cond
    [(null? lls) (list (list (car kv)(cdr kv)))]
    [(eq? (caar lls) (car kv)) 
     (cons (list (car kv) (cons (cadr kv) (cadar lls)))(cdr lls))]
    [else (cons (car lls)(addval kv (cdr lls)))]))

(define (group-by-key lls)
  (cond
    [(null? lls) '()]
    [else (addval (car lls) (group-by-key (cdr lls)))]))

我将如何编写下一步“每按键减少”？我也无法确定它是否需要两个参数或三个参数 .

到目前为止，我想出了：

(define (reduce-per-key reducef lls)
  (let loop ((val (car lls))
             (lls (cdr lls)))
    (if (null? lls) val
        (loop (reducef val (car lls)) (cdr lls)))))

但是，测试案例如：

(reduce-per-key
   (lambda (kv) (list (car kv) (length (cadr kv))))
   (group-by-key
     (map-per-key (lambda (kv) (list kv kv kv)) xs)))

我收到一个不正确的参数计数，但当我尝试用三个参数写它时，我也收到此错误 . 谁知道我做错了什么？

dictionary mapreduce scheme helper

1 回答

  • 1

    您的解决方案比它需要的复杂得多，并且有几个错误 . 事实上，正确的答案很简单，无法定义新的帮助程序 . 尝试解决这个解决方案的骨架，只需填写空白：

    (define (reduce-per-key reducef lls)
  (if (null? lls)        ; If the association list is empty, we're done
      <???>              ; and we can return the empty list.
      (cons (cons <???>  ; Otherwise, build a new association with the same key 
                  <???>) ; and the result of mapping `reducef` on the key's value
            (reduce-per-key <???> <???>)))) ; pass reducef, advance the recursion

    请记住，有一个用于在列表上映射函数的内置过程 . 像这样测试：

    (reduce-per-key (lambda (x) (* x x))
                '((x 1 2) (y 3) (z 4 5 6)))

> '((x 1 4) (y 9) (z 16 25 36))

    请注意，每个关联都由一个键（ car 部分）和一个列表作为其值（ cdr 部分）组成 . 例如：

    (define an-association '(x 3 6 9))
(car an-association)
> 'x       ; the key
(cdr an-association)
> '(3 6 9) ; the value, it's a list

    作为最后的想法，名称 reduce-per-key 有点误导， map-per-key 会更合适，因为这个程序可以使用 map 轻松表达...但这留给读者练习 .

    UPDATE:

    既然您已找到解决方案，我可以使用 map 建议更简洁的替代方案：

    (define (reduce-per-key reducef lls)
  (map (lambda (e) (cons (car e) (map reducef (cdr e))))
       lls))
    回复于

相关问题