ftp-peril.hs

-- Copyright © 2017 Bart Massey

-- | Illustrate the FTP problem in a realistic way.

import Data.List
import Data.Maybe

-- | Given a list of values `xs`, return a list of tuples
-- consisting of a list of `n` copies of a given value and a
-- count of its occurrences, ordered by value. Setting `n`
-- larger results in prettier histograms. For example:
--
-- >>> hist0 2 [7,3,5,5,3,3,5,3,3,7,7]
-- [([3,3],3),([5,5],1),([7,7],1)]
--
-- Algorithm: Sort the values, group them, and then
-- transform them into the desired form.
-- 
-- Sadly, this code is buggy. Spot the bug? It will compile
-- and run fine, but produce wrong answers.
--
-- >>> hist0 2 [3,5,7,3,3,4,2,3,3]
-- [([3,3],1),([5,5],1),([7,7],1)]
--
hist0 :: Ord a => Int -> [a] -> [([a], Int)]
hist0 n xs = 
    map process $ group $ sort xs
    where
      process ys =
          let parts = splitAt n ys in
          (fst parts, length parts)

-- | Bugfixed version of `hist`. Add the forgotten `snd`.
hist1 :: Ord a => Int -> [a] -> [([a], Int)]
hist1 n xs = 
    map process $ group $ sort xs
    where
      process ys =
          let parts = splitAt n ys in
          (fst parts, length $ snd parts)

-- | Cleaned up version of `hist1`. Make the implicit tuple
-- explicit, protecting against the `hist0` bug.
hist2 :: Ord a => Int -> [a] -> [([a], Int)]
hist2 n xs = 
    map process $ group $ sort xs
    where
      process ys =
          let (first, rest) = splitAt n ys in
          (first, length rest)

-- | Haskeller's version of `hist2`. Almost points-free.
-- Depends crucially on the FTP `Traversable` instance for
-- `(,)`.
hist3 :: Ord a => Int -> [a] -> [([a], Int)]
hist3 n = 
    map (fmap length . splitAt n) . group . sort


-- | Here's one any of us could do. Find the length of
-- the first nonempty sublist, returning 0 if no nonempty
-- sublists are present.
--
-- >>> fne0 ["", "", "abcde"]
-- 5
--
-- Again, though, not so much in practice.
--
-- >>> fne0 ["", "", "abcde"]
-- 1
--
-- Note that this function works fine on the empty
-- cases, since `length Nothing` is 0.
--
-- >>> fne0 ["", ""]
-- 0
--
-- >>> fne0 []
-- 0
--
-- It will also work coincidentally for the length-1 case.
--
-- >>> fne0 ["", "a"]
-- 1
--
fne0 :: [[a]] -> Int
fne0 = length . find (not . null)

-- | It's easy to forget that find returns a `Maybe`.
-- Especially when you're not getting any help from
-- the type system.
--
-- >>> fne1 ["", "", "abcde"]
-- 5
--
-- >>> fne1 ["", ""]
-- 0
--
fne1 :: [[a]] -> Int
fne1 = maybe 0 length . find (not . null)