平衡列表列表

Question

我正试图在Racket中列出由列表和列表列表组成的列表。原始列表如下所示：

'(((a 1) (b 2)) (c 3) ((d 4) (e 5)))

我需要它像：

'((a 1) (b 2) (c 3) (d 4) (e 5))

我尝试过flatten，concatenate等等，但我得到了不同的东西，但不是这个：

(define KK '(((a 1)(b 2))(c 3)((d 4)(e 5))))

(map(lambda(x)(if (list? x) x (list x)))(concatenate KK))

'((a 1) (b 2) (c) (3) (d 4) (e 5))

(map(lambda(x)x)(concatenate KK))

'((a 1) (b 2) c 3 (d 4) (e 5))

(map(lambda(x)(if (list? (car x)) (ormap(lambda(y)(when (list? y) y)) x) x))KK)

'((a 1) (c 3) (d 4))

(map(lambda(x)(if (list? (car x)) (andmap(lambda(y)(when (list? y) y)) x) 
x))KK)

'((b 2) (c 3) (e 5))

我越接近最后两个，但我有缺少的值，因为它是一个布尔映射。 Map将结果打包在一个列表中。

编辑：我的主要问题是列表是由一个函数创建的，根据输入，输出是一个列表或2到n列表的列表：

让名为H的列表由2到n个元素组成。让SPECS成为一个由列表组成的列表，其中包含与条件C匹配的H元素的可能组合。例如：

H='(a 1)

所以，作为'*在语义上意味着狂野汽车的符号，让H中的所有元素组合为：

HHs='((* *) (a *)(* 1) (a 1))

因此，SPECS是符合某些条件的HH，例如：'（（a）（1））

(map (lambda(S)(when  (<condition>)(set! NEWSET (append NEWSET S))))SPECS)

如果我追踪S，我会看到：

S1: (((*) (-inf.0 9) (2 +inf.0) (*)) ((*) (9 30) (2 +inf.0) (*)))
S2: ((*) (-inf.0 30) (2 +inf.0) (*))
S3: (((*) (-inf.0 30) (2 +inf.0) (no)) ((*) (-inf.0 30) (2 +inf.0) (si)))
S4: (((soleado) (-inf.0 30) (*) (*)) ((nublado) (-inf.0 30) (*) (*)) ((lluvioso) (-inf.0 30) (*) (*)))

因此，如果我将它们打包在列表中，我有：

'((((*) (-inf.0 9) (2 +inf.0) (*)) ((*) (9 30) (2 +inf.0) (*)))
   ((*) (-inf.0 30) (2 +inf.0) (*))
   (((*) (-inf.0 30) (2 +inf.0) (no)) ((*) (-inf.0 30) (2 +inf.0) (si)))
   (((soleado) (-inf.0 30) (*) (*)) ((nublado) (-inf.0 30) (*) (*)) ((lluvioso) (-inf.0 30) (*) (*))))

但我需要改为：

'(((*) (-inf.0 9) (2 +inf.0) (*)) ((*) (9 30) (2 +inf.0) (*))((*) (-inf.0 30) (2 +inf.0) (*))((*) (-inf.0 30) (2 +inf.0) (no)) ((*) (-inf.0 30) (2 +inf.0) (si))((sunny) (-inf.0 30) (*) (*)) ((cloudy) (-inf.0 30) (*) (*)) ((rainy) (-inf.0 30) (*) (*)))

（在（）中有列表的元素，它只是我算法的语义）。

问候

Answer 1

对于任意嵌套列表的一般情况，没有一个单线程的内置过程来解决这个问题。这是一个使用显式循环的可能解决方案，假设列表包含所有级别的双元素子列表：

(define (level-out lst)
  (let loop ([lst (flatten lst)])
    (if (empty? lst)
        '()
        (cons (list (first lst) (second lst))
              (loop (rest (rest lst)))))))

它按预期工作：

(level-out '(((a 1) (b 2)) (c 3) ((d 4) (e 5))))
=> '((a 1) (b 2) (c 3) (d 4) (e 5))

(level-out '((((((a 1)))))))
=> '((a 1))

(level-out '())
=> '()

(level-out '((a 1) (b 2) (c 3) (d 4) (e 5)))
=> '((a 1) (b 2) (c 3) (d 4) (e 5))

Answer 2

这是一个使用match的解决方案。请注意，这里的假设是我们提升的内部列表是两个事物的列表。

#lang racket

(require rackunit)

(define (flat-lift l)
  (match (flatten l)
    ['() '()]
    [(cons a (cons b c)) (cons (list a b) (flat-lift c))]))

(check-equal? (flat-lift '(((a 1) (b 2)) (c 3) ((d 4) (e 5))))
              '((a 1) (b 2) (c 3) (d 4) (e 5)))

(check-equal? (flat-lift '((((((a 1))))))) '((a 1)))

(check-equal? (flat-lift '()) '())

(check-equal? (flat-lift '((a 1) (b 2) (c 3) (d 4) (e 5)))
              '((a 1) (b 2) (c 3) (d 4) (e 5)))

Answer 3

如果您有一个谓词来确定何时不应该压缩子列表，那么您可以执行此操作。

;; An Element is a value for which element? returns true
;; element? : Any -> Boolean
(define (element? v)
  ...you-have-to-determine-this...)

这个element?谓词应该回答这个问题，“什么决定子列表何时不应该被夷为平地？”比如，(z 0)，(a 1)，(b 2)等在你的例子中并没有被夷为平地。到目前为止，其他答案都假设确定那些的是两元素列表，但是你已经说过子列表是1到n个元素。无论那些区别于普通嵌套列表的那些形状，你都应该定义element?来识别它。

如果你确定这个element?谓词，那么你可以根据它做一个flatten函数：

;; A NestedListofElement is one of:
;;  - Element
;;  - [Listof NestedListofElement]

;; flatten-elements : NestedListofElement -> [Listof Element]
(define (flatten-elements nle)
  (cond
    [(element? nle) (list nle)]
    [(list? nle)    (append-map flatten-elements nle)]))