Lexicographical Ordering (60/365)

> import Data.Ord (comparing)

This is completely random but I thought it was a neat use of laziness. You are familiar with lexicographical ordering? Haskell’s compare of lists implements this.

ghci> [1,2] < [1,3]
  True

ghci> [1,3,4] < [1,3,4,5]
  True

ghci> [2,4] < [2,3]
  False

Note that this favors shorter strings.

ghci> [1,2] < [1,2,3]
  True

ghci> [1,3] < [1,3,4]
  True

For whatever reason, I wanted to favor longer strings. How can we do this? First, note that the above is equivalent to doing the comparison after appending an infinite list of zeros to each operand (assuming we are using only positive numbers).

ghci> let aug xs = xs ++ cycle [0]
ghci> comparing aug [1,2] [1,3]
  LT

ghci> comparing aug [1,3,4] [1,3,4,5]
  LT

ghci> comparing aug [2,4] [2,3]
  GT

If I, instead, append an infinite list of a large number I can get what I want.

ghci> let aug xs = xs ++ cycle [9999999]
ghci> comparing aug [1,2] [1,2,3]
  GT

ghci> comparing aug [1,3] [1,3,4]
  GT
Advertisements
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s