1

简而言之，如何从 Common Lisp 中的字符串中获取不重复的字母列表？

例如：

"common"
-> ("c" "o" "m" "n") or in characters, (#\c #\o #\m #\n)
I'd care less about the order and type, if it is in string or character.

"overflow" -> (o v e r f l w)
"tomtomtom" -> (t o m)
   etc...

我的想法是收集原始字符串的第一个字母，然后使用该函数；

(remove letter string)

收集现在的第一个字母，删除字母字符串并将其附加到之前已经收集的字母中。这听起来像递归，但如果递归调用会丢失之前收集的 *letter*s 列表，对吗？我也怀疑是否有任何内置功能。

此外，我不想使用set或其中的任何一个，因为我想完全以函数式风格来做这件事。

谢谢你的时间。

4

3 回答 3

8 
CL-USER> (remove-duplicates (coerce "common" 'list))
(#\c #\m #\o #\n)

或者你甚至可以简单地这样做：

CL-USER> (remove-duplicates "common")
"comn"
于 2013-01-06T02:59:03.530 回答
0

如果您可以对您正在处理的文本做出一些假设，那么可能会有更好的可能性来做到这一点。例如，如果您只处理英文文本，那么您可以实现一个非常简单的哈希函数（基本上，使用 128 个元素长的位向量），这样您甚至不需要使用哈希表（即更复杂的结构）。下面的代码说明了这个想法。

(defun string-alphabet (input)
  (loop with cache =
       (coerce (make-array 128
                           :element-type 'bit
                           :initial-element 0) 'bit-vector)
     with result = (list input)
     with head = result
     for char across input
     for code = (char-code char) do
       (when (= (aref cache code) 0)
         (setf (aref cache code) 1
               (cdr head) (list char)
               head (cdr head)))
     finally (return (cdr result))))

(string-alphabet "overflow")
;; (#\o #\v #\e #\r #\f #\l #\w)

强制转换bit-vector并不是很重要，但它更容易调试（打印形式更紧凑），并且某些实现实际上可能会优化它以仅包含平台需要表示这么多位的这么多整数，即在128 位长度，在 64 位平台上，它可以短至 2 或 3 个整数长。

或者，你也可以这样做，使用整数：

(defun string-alphabet (input)
  (loop with cache = (ash 1 128)
     with result = (list input)
     with head = result
     for char across input
     for code = (char-code char) do
       (unless (logbitp code cache)
         (setf cache (logior cache (ash 1 code))
               (cdr head) (list char)
               head (cdr head)))
     finally (return (cdr result))))

但在这种情况下，在最坏的情况下，您将创建 128 个大整数，毕竟这并不昂贵，但位向量可能会做得更好。但是，这可能会给您一个提示，例如，当您可以假设只使用英文字母时（在这种情况下，可以使用比机器记忆字更短的整数）。

于 2013-01-06T07:45:09.360 回答
-5

这里有一些 Haskell 中的代码，因为我对 Lisp 不太熟悉，但由于它们都是功能性的，我认为翻译它不会有问题：

doit :: String -> String

doit [] = []
doit (x:xs) = [x] ++ doit (filter (\y -> x /= y) xs)

那么它有什么作用呢？你有一个字符串，如果它是一个空字符串（在 Haskell [] == "" 中），你返回一个empty字符串。否则，取第一个element并将其连接到对tail字符串的递归，但filter排除那些元素，即 == first element。

这个函数filter只是一个特定的语法糖map-function，在 Lisp 中称为remove-if你可以在这里重读：lisp filter out results from list not matching predicate

于 2013-01-06T01:30:08.180 回答