3
\$\begingroup\$

I'm trying to find pangrams ie sentences that contain all the letters of the alphabet, for instance "The quick brown fox jumps over the lazy dog".

I'm an absolute beginner in elisp, and it ended up being a really difficult exercice for me. My idea what to put all the letters in a set check if all the letters of the alphabet are in this set.

I don't think it was a very good idea because elisp doesn't seem to really have sets, so I ended up using a hashmap, which seems very clunky.

Another things that really bothers me is the two if in is-pangram. I feel that they make the function really difficult to reason about, although it's doing something very basic.

(defun add-to-hashmap (hashmap item)
  "Insert ITEM into HASHMAP and return HASHMAP."
  (puthash item t hashmap)
  hashmap)

(defun iter-hashmap-keys (hashmap)
  "Return a sequence of the keys in HASHMAP"
  (let ((keys '()))
    (maphash
     (lambda (key _) (setq keys (cons key keys)))
     hashmap)
    keys))

(defun get-letters (s)
  "Return the set of letters in S.
The set is a hashmap where keys are ascii characters and values are `t`."
  (setq letters (make-hash-table :test 'equal))
  (seq-reduce
   (lambda (hashmap letter) (add-to-hashmap hashmap (downcase letter)))
   (split-string s "")
   letters))

(defvar ALPHABET
  (let* ((letters (get-letters "abcdefghijklmnopqrstuvwxyz"))
         (_ (remhash "" letters)))
    letters))

(defun is-pangram (s)
  "Return `t` is S is a pangram, `nil` otherwise."
  (setq letters (get-letters s))
  (if (seq-some
       ;; this function returns returns `nil` if the given letter is
       ;; *present* in the set, and `t` otherwise. That way, seq-some
       ;; returns a non-nil value when there's a letter that is *not* in
       ;; the set.
       (lambda (letter) (if (gethash letter letters) nil t))
       (iter-hashmap-keys ALPHABET))
      nil
      t))

(provide 'pangram)
```
\$\endgroup\$
4
\$\begingroup\$
(setq letters (get-letters s))

You are setting the same letters variable from different functions; in Emacs Lisp, that sets a global variable which is bad style: (1) that pollutes the global namespace, (2) that could overwrite an existing variable, and (3) the functions are not reentrant and could lead to bad suprises with side-effects. Better introduce variables with let.

Instead of doing (remhash "" letters), you can pass T for OMIT-NULLS in split-string.

Another approach is to transform the input text so as to downcase all letters, remove spaces, remove duplicate letters and check if it corresponds to the expected alphabet. For example:

(equalp (delete-duplicates
         (sort (coerce
                (downcase
                 (remove ?\s "The quick brown fox jumps over the lazy dog"))
                'list)
               '<))
        (coerce "abcdefghijklmnopqrstuvwxyz" 'list))
\$\endgroup\$
  • \$\begingroup\$ Generic implementations of sort have a running time of O(n log n). It is possible to determine if a string is a panagram in O(n) time. This is not a case where sorting is cheaper than the big-O of the core problem. \$\endgroup\$ – ben rudgers Aug 13 at 19:25
1
\$\begingroup\$

At the high level bit, there's not much to complain about and a lot to like. Not so much because the code works (a necessary but non-trivial requirement for this site). But because the logic is sound (sets/hashmaps) and can be described and understood easily without a lot of details in the code. But I might be biased because I've written similar code to so solve somewhat similar problems in the past.

Code reveiew trope: performance

I want to be clear that I don't think performance matters much in this context. Firstly because the context is Emacs and second because it's in eLisp and third because this particular problem probably isn't all that important (even though the larger class of problems is important). If raw performance really mattered the code wouldn't be running in Emacs and even if it were we'd write it in C rather than eLisp.

But I find there is something unsettling about the solution.

Aesthetics/idioms

The eLisp way to implement sets is with lists. Using lists to represent sets is idiomatic. Using hashmaps is unidiomatic. And it feels unidiomatic.

The other issue is that hashmaps aren't idiomatic math. Sets are. Whether we use lists or hashmaps to implement the set abstraction, wrapping the implementation in the language of sets makes it clearer what we are doing.

;; add-to-hashmap (hashmap item) ...
;; becomes

(defun add-element-to-set (set element)
  "Insert ELEMENT into SET and return SET."
  (puthash element t set)
  set)

layering abstractions is even more idiomatic:

 (setf 'set-insert (function puthash))

helps the set abstraction permeate deeper into code

(defun add-element-to-set (set element)
  "Insert ELEMENT into SET and return SET."
  (set-insert element t set) ;;; CHANGED
  set)

On the other hand, some people see this idiom as a bug not a feature.

About performance

The reason lists are idiomatic for sets (and many other things in Lisp) is because a lot of the time, lists are good enough. Checking if a string is a panagram inside of Emacs is probably one of those times. Suppose we use the procedure.

;;; PROGRAM ONE
(defun panagram? (sentence)
      (let (s (upcase sentence))
      (and
        (string-match "A" s)
        (string-match "B" s)
        ...
        (string-match "Z" s))))

Implementation details aside, this blunt force form is O(n) time and space. Because each letter in the input matters (at least in theory) we can't get better than O(n).

About hashmaps

O(1) time for lookups and insertions makes hashmaps attractive for many implementations. But the O(1) is amortized. Inserting n elements into a hashmap takes O(n) time. Reading each of those n elements also takes O(n) time. Hashmaps are only more efficient when we make many more reads than insertions. But here we have n insertions into and n reads from the hashmap before it gets garbage collected. There's no amortization. Using hashmaps is not a performance optimization.

But hashing is more than hashmaps. So is mapping.

Mapping and Hashing

If we had a wishing well, after we wished for more wishing wells, we might wish for a hash function that hashes our string into the boolean panogram?. Wait a minute, at the high level, that's what the problem is. It's just at the high level, the hash of the input string is a hashmap of characters rather than a simpler data structure that's easier to unpack. Let's be fearless and try writing our own hash function.

Hashing with primes

The first 26 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101. Their product is 1267259750580658434. Pseudo-code for panagram?

### PROGRAM TWO ###
product = 1
primes = array[2 3 5 ...101]
foreach character in string
  product = product * primes[downcase(character) - 97]
return product modulo 1267259750580658434 == 0

avoids allocating the hash map, writing to it, and reading from it. Hashing at the level of the string rather than the character is generally simpler. The use of prime factors makes it a little more clever than is ideal. It requires more mental effort to understand than the blunt approach using (and ...) or the use of hashmaps. It might not be worth it. But it might be a step in the right direction

PROGRAM TWO has some useful attributes:

  • The reduction is simple. It compresses the string into an easily interpreted value.
  • It utilizes the lexographic order inherent in the alphabet to map characters to values in an array.
  • It reflects the boundaries of the input domain (26 characters). This is also true for PROGRAM ONE.
  • Thinking about the characteristics of the input is a good thing. For example strings of less than 26 characters cannot be panagrams.

Simpler hashing

Using prime factorization is a generic approach that scales all the way out to things like Git source control and https. But like hashmaps, it feels like overkill here. There are simpler ways to record whether or not a character occurs in a string. All we need is one bit...

...but bitwise operations are a bit low level for elisp and emacs, so maybe we simulate them.

### PROGRAM THREE ###
bitmap = [0]
do 25 times
  append 0 to bitmap # array length 26 all zeros
foreach character in string
  bitmap[downcase(character) - 97] = 1
return reduce(bitmap 0 '#+) == 26

Remarks

What makes this problem potentially interesting is that we have to start thinking about properties of the data. For example, no string less than 26 characters can possibly be a pangram. And not only do we know that most strings are not pangrams we know the most likely ways in which they are not pangrams...such as missing q or z or x.

That means we might come back to PROGRAM ONE and refactor the (and ...) to

;;; PROGRAM FOUR ;;;
(defun panagram? (sentence)
  (let (s (upcase sentence))
  (and
    (string-match "Q" s)
    (string-match "Z" s)
    ...
    (string-match "E" s)))) 

Most ordinary sentences will be rejected by the first string-match and nearly all sentences would be rejected if the first regex was [QZXJ].

To put it another way, if we represent each character as one bit in a bitmap, there are 226-1 bitmaps that are not pangrams and only one that is. Finding pangrams efficiently correlates with rejecting strings quickly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.