在球拍中以 "creative" 的方式反转一个简单的函数

Question

我需要一些帮助:D.

我已经编写了这个将字符串转换为数字列表的程序：

(define (string->encodeable string)
   (map convert-to-base-four (map string->int (explode string))))

我需要一个完全相反的函数。换句话说，获取以 4 为底数的数字列表，将其转换为以 10 为底数，然后创建一个字符串。是否有 "creative" 方法来反转我的函数，或者我是否必须重新编写每个相反的步骤。非常感谢您的帮助。

Answer 1

取决于你如何定义"creative"。在 Racket 中你可以这样做：

(define (f lst)
  (number->string
   (for/fold ([r 0]) ([i (in-list lst)])
     (+ i (* r 4)))))

然后

> (f '(1 0 0))
"16"
> (f '(1 3 2 0 2 1 0 0 0))
"123456"

Answer 2

使用 SRFI-1 List library

的标准 Scheme 实现

#!r6rs
(import (rnrs base)
        (only (srfi :1) fold))

(define (base4-list->number b4l)
  (fold (lambda (digit acc)
          (+ digit (* acc 4)))
        0
        b4l))

(base4-list->number '(1 2 3))
; ==> 27

它在 #lang racket 中的工作原理相同，但你 (require srfi/1)

PS：我不完全确定从 10 进制到 4 进制的转换是否是最佳解决方案。想象一下 95 应该变成 (1 1 3 3) 的数字。我会在 SRFI-1 中使用 unfold-right 来完成它。

Answer 3

您正在寻找的关系称为 isomorphism

这里的其他答案使用折叠来证明这一点，但在您的水平上，我认为您应该自己做——或者至少在您更熟悉该语言之前

#lang racket

(define (base10 ns)
  (let loop ((ns ns) (acc 0))
    (if (empty? ns)
        acc
        (loop (cdr ns) (+ (car ns)
                          (* 4 acc))))))

(displayln (base10 '(3 0)))               ; 12
(displayln (base10 '(3 1)))               ; 13
(displayln (base10 '(3 2)))               ; 14
(displayln (base10 '(3 3)))               ; 15
(displayln (base10 '(1 0 0)))             ; 16
(displayln (base10 '(1 3 2 0 2 1 0 0 0))) ; 123456

Answer 4

@naomik 的回答提到了 isomorphisms。当你构造一个同构时，你是在构造一个函数和它的反函数。通过将同构组合和连接在一起，您可以构造两个方向 "at once."

;; Converts between a base 4 list of digits (least significant first, most
;; significant last) and a number.
(define iso-base4->number
  (iso-lazy
   (iso-cond

     ;; an iso-cond clause has an A-side question, an A-to-B isomorphism,
     ;; and a B-side question. Here the A-side is empty and the B-side is 
     ;; zero.
     [empty?  (iso-const '() 0)  zero?]

     ;; Here the A-side is a cons, and the B-side is a positive number.
     [cons?
      (iso-join
        cons
        (λ (r q) (+ (* 4 q) r))
        [first  iso-identity       (curryr remainder 4)]
        [rest   iso-base4->number  (curryr quotient 4)])
      positive?])))

此代码包含将 4 进制列表转换为数字并再次转换回数字所需的所有信息。（这里的base 4 lists是从最低位到最高位排序的，这和正常的方向相反，不过没关系，可以在外面固定。）

第一个 cond 案例将空映射为零，然后再映射回来。

第二个 cond 案例将 (cons r q) 映射到 (+ (* 4 q) r) 并再次映射回来，但是 q 在列表和数字之间递归地转换。

正如可以使用 first 和 rest 拆分 cons 单元格一样，正数可以拆分为 "remainder-wrt-4" 和 "quotient-wrt-4"。由于余数是固定大小而商是任意大小，因此 remainder 类似于 first 而 quotient 类似于 rest.

first和remainder不需要相互转换，所以第一个iso-join子句使用了iso-identity，什么都不做的同构。

[first  iso-identity       (curryr remainder 4)]

rest 和 quotient 确实需要转换。剩下的是一个以 least-to-most-significant 顺序排列的基数 4 数字的列表，商是它对应的数字。它们之间的转换是iso-base4->number.

[rest   iso-base4->number  (curryr quotient 4)]

如果您对 iso-const、iso-cond 和 iso-join 等同构形式的定义方式感兴趣，this gist 包含此示例所需的一切。

在球拍中以 "creative" 的方式反转一个简单的函数

Reversing a simple function in a "creative" way in racket

scheme

reverse

racket