缺点框实现 [英] Cons box implementation

问题描述

我似乎无法找到一种在 Ruby 中执行 Scheme 的 cons 框的方法(似乎它几乎是所有数组).这是一个非常粗略的概述:

I cannot seem to figure out a way to do Scheme's cons boxes in Ruby (it seems its pretty much all arrays). This is a pretty rough outline:

class cons
    def initialize (car, cdr)
    @car = car
    @cdr = cdr
    end

    #return the car of the pair
    def car
        return @car
    end

    #return the cdr of the pair
    def cdr
        return @cdr
    end
end

我可以传递两个值并调用 car 和 cdr，但这不是任何类型的列表(只有两个值).如何制作一个列表，我可以在其中插入一些内容，如 Scheme cons:

I can pass two values and call the car and cdr, but this is not a list of any sort (just two values). How do I make a list on which I can insert something as in Scheme cons:

myCons = (cons(1, cons(2, cons(3, cons(4, 5)))))

我能找到的最接近的是制作我自己的数组，如 myArray = Array[1, 2, 3, 4, 5] 然后使用 puts myArray.join(' ').这只给了我 "1 2 3 4 5" 而不是 (1 2 3 4 5) ，这还没有考虑到我仍然无法实际构建有缺点的数组，我只是自己做的.

The closest I can find is making my own array like myArray = Array[1, 2, 3, 4, 5] and then using puts myArray.join(' '). This only gives me "1 2 3 4 5" and not (1 2 3 4 5) though, and that's not taking into account I still can't actually build the array with cons, I simply made it myself.

推荐答案

这里是 Cons 的一个实现，它有一个不错的内置打印语法(包括对不正确列表的支持)，并且是可枚举的:

Here's an implementation of Cons that has a decent print syntax built-in (including support for improper lists), and is enumerable:

class Cons
  include Enumerable
  attr_accessor :car, :cdr

  class << self
    alias [] new
  end

  def initialize(car, cdr)
    self.car = car
    self.cdr = cdr
  end

  def each_pair
    return to_enum(:each_pair) unless block_given?
    cell = self
    while cell.is_a? Cons
      yield cell.car, cell.cdr
      cell = cell.cdr
    end
  end

  def each
    return to_enum unless block_given?
    each_pair { |car,| yield car }
  end

  def print
    sb = '('
    each_pair do |car, cdr|
      sb << yield(car)
      case cdr
      when Cons
        sb << ' '
      when nil
      else
        sb << ' . ' << yield(cdr)
      end
    end
    sb << ')'
  end

  def to_s
    print &:to_s
  end

  def inspect
    print &:inspect
  end
end

哦，这是创建列表的简单方法(类似于 Common Lisp 和 Scheme 中的 list 函数):

Oh, and here's an easy way to create a list (similar to the list function found in both Common Lisp and Scheme):

def list(*items)
  items.reverse_each.reduce(nil) { |result, item| Cons[item, result] }
end

示例:

irb(main):001:0> a = Cons[1, Cons[2, Cons[3, nil]]]
=> (1 2 3)
irb(main):002:0> b = Cons[1, Cons[2, Cons[3, 4]]]
=> (1 2 3 . 4)
irb(main):003:0> a.to_a
=> [1, 2, 3]
irb(main):004:0> a.map(&Math.method(:sqrt))
=> [1.0, 1.4142135623730951, 1.7320508075688772]
irb(main):005:0> list(1, 2, 3, 4, 5)
=> (1 2 3 4 5)

<小时>

更新:一位用户给我写信询问如何(除其他外)附加基于 cons 的列表.作为一名 Schemer，我喜欢将 cons 单元视为不可变的，因此附加的标准方法是将每个元素从右到左从左侧列表添加到右侧列表中.下面是我将如何实现它.

---

Update: A user wrote me asking how to (among other things) append cons-based lists. As a Schemer, I like to treat cons cells as immutable, so the standard approach for appending is to cons each element, right-to-left, from the left-hand list onto the right-hand list. Here's how I would implement it.

首先，让我们定义一个 reduce_right 方法.(从技术上讲，这是一个正确的折叠，而不是一个正确的减少，但 Ruby 更喜欢术语减少"而不是折叠"，所以这就是我在这里使用的.) 我们将重新打开 NilClass 和 Cons 以使其工作:

First, let's define a reduce_right method. (Technically, this is a right fold, not a right reduce, but Ruby prefers the term "reduce" rather than "fold", so that's what I'll use here.) We'll reopen both NilClass and Cons to make this work:

class NilClass
  def reduce_right(init)
    init
  end
end

class Cons
  def reduce_right(init, &block)
    block.call(cdr.reduce_right(init, &block), car)
  end
end

那么，append 就像使用 reduce_right 一样简单:

Then, append is as simple as using reduce_right:

def append(lhs, rhs)
  lhs.reduce_right(rhs) { |result, item| Cons[item, result] }
end

这允许你附加两个列表，但通常，允许附加任意数量的列表更方便(这是 Scheme 的 append 允许的):

This allows you to append two lists, but usually, it's more handy to allow appending any number of lists (and this is what Scheme's append allows):

def append(*lists)
  lists.reverse_each.reduce do |result, list|
    list.reduce_right(result) { |cur, item| Cons[item, cur] }
  end
end

请注意，在这两种情况下，最右边的列表"不需要是正确的列表，您可以通过在其中放置不是 cons 单元格的内容来创建不正确的列表:

Notice that in both cases, the rightmost "list" is not required to be a proper list, and you can create improper lists by putting something that's not a cons cell there:

irb(main):001:0> append(list(1, 2, 3), list(4, 5))
=> (1 2 3 4 5)
irb(main):002:0> append(list(1, 2, 3), list(4, 5), 6)
=> (1 2 3 4 5 . 6)
irb(main):003:0> append(list(1, 2, 3), list(4, 5), list(6))
=> (1 2 3 4 5 6)

(非最右边的列表必须是正确的列表.)

(Non-rightmost lists must be proper lists.)

这篇关于缺点框实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！