问scheme怎么实现迭代版的map

(define (map p l)
  (if (null? l)
      nil
      (cons (p (car l))
	    (map p (cdr l)))))

scheme好像没有把原子插入列表尾部的操作,只能插入到前面,有没有迭代版的map??

(append '(a b c) (list 'd)) ;; (a b c d)

Scheme 沒有迭代。想要 "迭代“ 也得先实现 map 类似的东西

那换一种说法吧,尾递归

map 哪来的尾递归实現?你怕不是以为所有递归都能写成尾递归?

(define (map-iter p l)
  (define (iter li result)
    (if (null? li)
        (reverse result)
        (iter (cdr li) (cons (p (car li)) result))))
  (iter l '()))
1赞

Lisp的list是抽象数据类型(Abstract Data Type),拓扑结构类似LinkedList,这决定了刻意在尾部添加元素的做法是低效的

双 链 表 !

data List a = Nil | List a 这是lisp的list,是哪门子的双链表?

可以 setcdr


@zhouchongzxc

(define (map-one p l)
  (let ((aux (lambda (aux head tail l)
	       (if (nil? l) head
		   (begin (setcdr tail (p (car l)))
			  (aux aux head (cdr tail) (cdr l)))))))
    (when (pair? l)
      (let ((head (cons (p (car l)) nil)))
	(aux aux head head (cdr l))))))

对于这个问题不需要跑尾部加啊 @cireu

如果所有的自然数都是通过 0 和 +1组成

那你怎么得到负数呢

cdr 是 (nth 1) 不是尾部

把尾部存起来,每次迭代时更新不就行了。

给 个 代 码

:man_facepalming:

服了,负数是自然数?

双链表不是列表

你可以自己重新发明个语言把双链表当成基础设施实现一下。

另外请不要继续在本楼纠结列表/双链表问题,这已经偏离了主题


你首先要找到这个cdr的位置,找这个位置的时间复杂度就是O(n)了,直接在头部加上新元素时间复杂度就是O(1)

你的帖子已经被社区标记并被临时隐藏。

稍微补充下:

data List a = Nil | Cons a (List a)

@glgl-schemer 稍微修正下:

(define (map-one p l)
  (let ((aux (lambda (aux head tail l)
	       (if (nil? l) head
		   (begin (setcdr tail (cons (p (car l)) nil))
			  (aux aux head (cdr tail) (cdr l)))))))
    (when (pair? l)
      (let ((head (cons (p (car l)) nil)))
	(aux aux head head (cdr l))))))

另外如果用set-car!的话,空间复杂度都不用那么高

(define (map-set p l)
  (define (iter li)
    (cond ((null? li) l)
          (else
           (set-car! li (p (car li)))
           (iter (cdr li)))))
  (iter l))

讨论个数据结构都讨论不了

那还是讨论指法 键盘 抄配置 吧

如果你想讨论双链表,你可以单独开一帖探讨。这贴不是一个讨论数据结构的帖子,是一个讨论对于特定数据结构的算法的帖子。不适合发散讨论其他数据结构

阴阳怪气说怪话对讨论本身是没有任何好处的