{- |
Description: Sorting a list of lists according to length of sublists
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P28" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P28 (lsort, lfsort) where

import           Data.List     (sortOn)
import           Data.Map.Lazy ((!))
import qualified Data.Map.Lazy as Map

-- | We suppose that a list contains elements that are lists themselves.
-- Write a function to sort the elements of this list according to their length,
-- i.e., short lists first and longer lists later.
lsort :: [[a]] -> [[a]]
lsort :: forall a. [[a]] -> [[a]]
lsort = ([a] -> Int) -> [[a]] -> [[a]]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length

-- | Again, we suppose that a list contains elements that are lists themselves.
-- But this time, write a function to sort the elements of this list according to their length frequency,
-- i.e., lists with rare lengths are placed first, others with a more frequent length come later.
lfsort :: [[a]] -> [[a]]
lfsort :: forall a. [[a]] -> [[a]]
lfsort [[a]]
xs = ([a] -> Int) -> [[a]] -> [[a]]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn (\[a]
ys -> Map Int Int
fs Map Int Int -> Int -> Int
forall k a. Ord k => Map k a -> k -> a
! [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
ys) [[a]]
xs
  where fs :: Map Int Int
fs = (Int -> Int -> Int) -> [(Int, Int)] -> Map Int Int
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) ([(Int, Int)] -> Map Int Int) -> [(Int, Int)] -> Map Int Int
forall a b. (a -> b) -> a -> b
$ ([a] -> (Int, Int)) -> [[a]] -> [(Int, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (\[a]
ys -> ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
ys, Int
1 :: Int)) [[a]]
xs