排序算法lisp-scheme

Question

我决定学习一些函数式语言,毕竟我与lisp-scheme联系起来.

我正在尝试创建一个函数来检查列表是否已排序,或者最低的第一个越来越高,反之亦然,如果它可以被排序,它应该返回true,否则为false.

这是我的第一个代码,仅在列表增加(或相等)时才起作用.

    (define sorted?
     (lambda (lst)
      (cond ((empty? lst) #t)
            (else (and (<= (car lst) (cadr lst))
                  (sorted? (cdr lst)))))))

澄清:像(排序？'(1 2 3 4 5))和(排序？'(5 4 3 2 1))之类的东西应该返回true,否则如果当然没有排序错误.

在以函数式编程时我应该如何思考？语法似乎很简单,但我不习惯逻辑.

Answer 1

你几乎做对了,看:

(define sorted?
  (lambda (lst)
    (cond ((or (empty? lst) (empty? (cdr lst)))
           #t)
          (else (and (<= (car lst) (cadr lst))
                     (sorted? (cdr lst)))))))

在基本情况下进行一点修改,你就完成了.当列表中只剩下一个元素时,必须停止,否则cadr表达式将抛出错误.

对于问题的第二部分:如果要检查它是否使用不同的标准进行排序,只需将比较函数作为参数传递,如下所示:

(define sorted?
  (lambda (lst cmp)
    (cond ((or (empty? lst) (empty? (cdr lst)))
           #t)
          (else (and (cmp (car lst) (cadr lst))
                     (sorted? (cdr lst) cmp))))))

(sorted? '(1 2 3 4 5) <=)
> #t
(sorted? '(5 4 3 2 1) >=)
> #t

现在,如果你想知道一个列表的排序或者升序或降序排列:

(define lst '(1 2 3 4 5))
(or (sorted? lst >=) (sorted? lst <=))
> #t

如您所见,函数式编程是将过程定义为尽可能通用,并将它们组合起来解决问题.您可以将函数作为参数传递的事实对于实现泛型函数有很大帮助.

Answer 2

具体实施

我会接受ÓscarLópez的回答并更进一步:

(define sorted? (lambda (lst)
  (letrec ((sorted-cmp 
            (lambda (lst cmp)
              (cond ((or (empty? lst) (empty? (cdr lst)))
                     #t)
                    (else (and (cmp (car lst) (cadr lst))
                               (sorted-cmp (cdr lst) cmp)))))))
    (or (sorted-cmp lst <=) (sorted-cmp lst >=)))))

这个版本与他的最大区别在于,sorted?现在将Óscar的版本定义为内部帮助函数,letrec并使用和调用它.

功能性思维

您实际上选择了一个很好的示例来说明Scheme如何查看世界的某些方面,并且您的实现是一个非常好的开始.

解决这个问题的一个重要功能原则是,你可以放置任何东西(**here** more stuff '(1 2 3 4)),你可以作为参数传递给另一个函数.也就是说,函数是函数式编程语言中的第一类.因此,您<=在比较中使用的事实意味着您可以将<=参数作为参数传递给另一个进行相应比较的函数.Óscar的回答很好地说明了这一点.

体现另一种常见功能模式的该问题的另一方面是主要由(cond)块组成的功能.在许多函数式编程语言(Haskell,ML,OCaml,F#,Mathematica)中,默认情况下,您将获得比模式匹配更强的模式匹配能力.因此,(cond)在Scheme中,您必须描述如何测试您寻找的模式,但这通常是相当简单的(例如(or (empty? lst) (empty? (cdr lst)))在此实现中).

我认为在这个问题中体现的最后一个函数式编程模式是许多函数式编程解决方案是递归的.递归是我必须使用letrec而不是普通ol'的原因let.

几乎所有你可以通过操作第一个元素(或本例中的2个元素)然后cdr在列表的tail()上重复操作来执行此操作.方案中的命令式for或while风格循环并非不可能(虽然它们在Haskell等纯函数式语言中几乎不可能),但在许多情况下它们在Scheme中略显不合适.但是Scheme的灵活性允许您作为开发人员做出决策,从而在某些情况下实现重要的性能或可维护性优化.

继续探索

我sorted?在这里回答的第一个实现是sorted-cmp根据它在列表中看到的内容决定传递哪个比较运算符.当我发现列表可以从两个相同的数字开始时,我退缩了'(1 1 2 3 4 5).但是,当我更多地考虑它时,肯定有一种方法可以跟踪你是否已经确定了一个方向,因此只需要一个电话sorted-cmp.您可以考虑下一步探索.