Rhyming Sort
December 8, 2020
I recently found on the internet a delightful paper by Kenneth Ward Church called Unix™ for Poets that provides an introduction to the Unix command line utilities for text processing. The paper must be ancient, because it gives the author’s email address at research.att.com, but I’ve never seen it before. One of the examples in the paper is rhyming sort, in which words are sorted from the right rather than the left; the left column below is in normal alphabetical order, the right column is in rhyming order:
falsely freely
fly sorely
freely surely
sorely falsely
surely fly
Church says:
“freely” comes before “sorely” because “yleerf” (“freely” spelled backwards) comes before “yleros” (“sorely” spelled backwards) in lexicographic order. Rhyming dictionaries are often used to help poets (and linguists who are interested in morphology).
Church solved the problem with a rev | sort | rev pipeline.
Your task is to sort a file containing one word per line into rhyming order. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Here is a “one-liner” using standard R7RS Scheme and a couple of well
known helpers that seems very close in spirit to the Unix pipeline
solution. In comparing it to the solution by @programmingpraxis, one
difference is that this one makes only Theta(n) string-reversals
instead of Theta(n log n). Based on some very quick tests on larger
inputs (e.g., /usr/share/dict/words on Debian GNU/Linux), the
difference can be quite significant (10x).
(import (scheme base) (scheme write) (only (srfi 13) string-reverse) (only (srfi 132) list-sort)) (define sample '("falsely" "fly" "freely" "sorely" "surely")) (define (rhyming-sort strs) (map string-reverse (list-sort string<? (map string-reverse strs)))) (display sample) (newline) (display (rhyming-sort sample)) (newline)Output:
We might as well use some actual poetry for our test data, so here is some Chaucer. After sanitizing the text, reverse all words, sort with appropriate collation (to get, for example, ‘vertú’ in the right place – Unicode combining characters might be a problem), and reverse again before final output:
import locale s = """ Whan that Aprille with his shoures soote, The droghte of March hath perced to the roote, And bathed every veyne in swich licóur Of which vertú engendred is the flour; Whan Zephirus eek with his swete breeth Inspired hath in every holt and heeth The tendre croppes, and the yonge sonne Hath in the Ram his halfe cours y-ronne, And smale foweles maken melodye, That slepen al the nyght with open ye, So priketh hem Natúre in hir corages, Thanne longen folk to goon on pilgrimages, And palmeres for to seken straunge strondes, To ferne halwes, kowthe in sondry londes; And specially, from every shires ende Of Engelond, to Caunterbury they wende, The hooly blisful martir for to seke, That hem hath holpen whan that they were seeke. """ locale.setlocale(locale.LC_COLLATE,'en_GB.UTF-8') words = set(w.rstrip(';,.')[-1::-1] for w in s.lower().split()) print(" ".join(s[-1::-1] for s in sorted(words, key=locale.strxfrm))) # perced bathed engendred inspired and engelond ende wende halfe yonge # straunge the kowthe seeke seke smale aprille thanne y-ronne sonne # ferne veyne tendre were natúre swete droghte roote soote ye melodye # of which swich march hath heeth breeth priketh with eek folk al # blisful ram hem from whan longen maken seken slepen holpen open in # on goon so to hir martir for licóur flour londes strondes # pilgrimages corages foweles croppes palmeres shires shoures halwes # is his cours zephirus that nyght holt vertú they specially hooly # sondry every caunterburyKlong
str::["falsely" "fly" "freely" "sorely" "surely"] ["falsely" "fly" "freely" "sorely" "surely"] {|x}'str2@<str2::{|x}'?str ["freely" "sorely" "surely" "falsely" "fly"]Adopting Chaucer’s sample text (Thanks, @matthew), I get the following:
str ["whan" "that" "aprille" "with" "his" "shoures" "soote" "the" "droghte" "of" "march" "hath" "perced" "to" "the" "roote" "and" "bathed" "every" "veyne" "in" "swich" "licóur" "of" "which" "ertú" "engendred" "is" "the" "flour" "whan" "zephirus" "eek" "with" "his" "swete" "breeth" "inspired" "hath" "in" "every" "holt" "and" "heeth" "the" "tendre" "croppes" "and" "the" "yonge" "sonne" "hath" "in" "the" "ram" "his" "halfe" "cours" "y-ronne" "and" "smale" "foweles" "maken" "melodye" "that" "slepen" "al" "the" "nyght" "with" "open" "ye" "So" "priketh" "hem" "natúre" "in" "hir" "corages" "thanne" "longen" "folk" "to" "goon" "on" "pilgrimages" "and" "palmeres" "for" "to" "seken" "straunge" "strondes" "to" "ferne" "halwes" "kowthe" "in" "sondry" "londes" "and" "specially" "from" "every" "shires" "ende" "of" "engelond" "to" "caunterbury" "they" "wende" "the" "hooly" "blisful" "martir" "for" "to" "seke" "that" "hem" "hath" "holpen" "whan" "that" "they" "were" "seeke"] {|x}'str2@<str2::{|x}'?str ["perced" "bathed" "engendred" "inspired" "and" "engelond" "ende" "wende" "halfe" "yonge" "straunge" "the" "kowthe" "seeke" "seke" "smale" "aprille" "thanne" "y-ronne" "sonne" "ferne" "veyne" "tendre" "were" "natúre" "swete" "droghte" "roote" "soote" "ye" "melodye" "of" "which" "swich" "march" "hath" "heeth" "breeth" "priketh" "with" "eek" "folk" "al" "blisful" "ram" "hem" "from" "whan" "longen" "maken" "seken" "slepen" "holpen" "open" "in" "on" "goon" "So" "to" "hir" "martir" "for" "flour" "licóur" "londes" "strondes" "pilgrimages" "corages" "foweles" "croppes" "palmeres" "shires" "shoures" "halwes" "is" "his" "cours" "zephirus" "that" "nyght" "holt" "they" "specially" "hooly" "sondry" "every" "caunterbury" "ertú"]A common lisp solution.
(defun read-file-into-list (file-path) "return an ordered list of strings of each line in file-path" (with-open-file (in file-path) (loop for line = (read-line in nil) while line collect line))) (defun rhyming-sort (data-list) (sort data-list #'(λ (s u) (string-lessp (reverse s) (reverse u)))))