在方案中实现 powerset
Implementing powerset in scheme
我正在尝试以两种方式在 Scheme 中实现幂集函数。
一种方法是使用尾递归,我是这样做的:
(define (powerset list)
(if (null? list) '(()) ;; if list is empty, its powerset is a list containing the empty list
(let ((rest (powerset (cdr list)))) ;; define "rest" as the result of the recursion over the rest of list
(append (map (lambda (x) (cons (car list) x)) rest) ;; add the first element of list to the every element of rest (which is a sublist of rest)
rest)))) ;; and append it to rest itself (as we can either use the current element (car list), or not
效果很好。
另一种方法是使用 foldr,这是我遇到一些问题的地方。
我目前的实现如下:
(define (powerset-fr list)
(foldr (lambda (element result) ;; This procedure gets an element (and a result);
(if (null? result) ;; if starting with the empty list, there is nothing to "fold over".
(cons '() (cons element result))
(foldr (lambda (inner-element inner-result)
(append (cons element result) inner-result))
'(())
result)))
'() ;; The result is initialized to the empty list,
list)) ;; and the procedure is being applied for every element in the first list (list1)
结果很差。
我将尽快解释到目前为止我是如何解决这个问题的:
foldr 遍历给定集合中的每个元素。对于每个这样的元素,我应该向幂集中添加一些新元素。
这些应该是哪些元素? powerset 中每个现有元素的一个新元素,其中将列表中的当前元素附加到 powerset 中的现有元素。
这就是为什么我认为我应该以嵌套方式使用 foldr 两次 - 一次遍历给定列表中的所有项目,对于每个项目我使用 foldr 遍历"result"(当前功率组)中的所有项目。
我遇到了空列表的问题(没有任何东西被添加到 powerset),因此添加了 "if" 部分(而不仅仅是 foldr),但它也不能很好地工作。
我想就是这样。我感觉很接近,但它仍然非常具有挑战性,所以我们欢迎每一个帮助。
谢谢!
解决方案更简单,不需要使用双 foldr
,试试这个:
(define (powerset-fr lst)
(foldr (lambda (e acc)
(append (map (lambda (x) (cons e x))
acc)
acc))
'(())
lst))
如果您的解释器定义了 append-map
或类似的东西,那么解决方案会更短一些 - 结果的顺序会有所不同,但这并不重要:
(define (powerset-fr lst)
(foldr (lambda (e acc)
(append-map (lambda (x) (list x (cons e x)))
acc))
'(())
lst))
无论哪种方式,它都按预期工作:
(powerset-fr '(1 2 3))
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())
我正在尝试以两种方式在 Scheme 中实现幂集函数。 一种方法是使用尾递归,我是这样做的:
(define (powerset list)
(if (null? list) '(()) ;; if list is empty, its powerset is a list containing the empty list
(let ((rest (powerset (cdr list)))) ;; define "rest" as the result of the recursion over the rest of list
(append (map (lambda (x) (cons (car list) x)) rest) ;; add the first element of list to the every element of rest (which is a sublist of rest)
rest)))) ;; and append it to rest itself (as we can either use the current element (car list), or not
效果很好。
另一种方法是使用 foldr,这是我遇到一些问题的地方。 我目前的实现如下:
(define (powerset-fr list)
(foldr (lambda (element result) ;; This procedure gets an element (and a result);
(if (null? result) ;; if starting with the empty list, there is nothing to "fold over".
(cons '() (cons element result))
(foldr (lambda (inner-element inner-result)
(append (cons element result) inner-result))
'(())
result)))
'() ;; The result is initialized to the empty list,
list)) ;; and the procedure is being applied for every element in the first list (list1)
结果很差。
我将尽快解释到目前为止我是如何解决这个问题的:
foldr 遍历给定集合中的每个元素。对于每个这样的元素,我应该向幂集中添加一些新元素。 这些应该是哪些元素? powerset 中每个现有元素的一个新元素,其中将列表中的当前元素附加到 powerset 中的现有元素。
这就是为什么我认为我应该以嵌套方式使用 foldr 两次 - 一次遍历给定列表中的所有项目,对于每个项目我使用 foldr 遍历"result"(当前功率组)中的所有项目。
我遇到了空列表的问题(没有任何东西被添加到 powerset),因此添加了 "if" 部分(而不仅仅是 foldr),但它也不能很好地工作。
我想就是这样。我感觉很接近,但它仍然非常具有挑战性,所以我们欢迎每一个帮助。 谢谢!
解决方案更简单,不需要使用双 foldr
,试试这个:
(define (powerset-fr lst)
(foldr (lambda (e acc)
(append (map (lambda (x) (cons e x))
acc)
acc))
'(())
lst))
如果您的解释器定义了 append-map
或类似的东西,那么解决方案会更短一些 - 结果的顺序会有所不同,但这并不重要:
(define (powerset-fr lst)
(foldr (lambda (e acc)
(append-map (lambda (x) (list x (cons e x)))
acc))
'(())
lst))
无论哪种方式,它都按预期工作:
(powerset-fr '(1 2 3))
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())