View Subcategory
Maps
Algorithms

Create a histogram map from a list

Given the list [a,b,a,c,b,b], produce a map {a:2, b:3, c:1} which contains the count of each unique item in the list
haskell
import Data.List
import qualified Data.Map as Map

histogram :: Ord a => [a] -> Map.Map a Int
histogram xs = Map.fromList [ (head l, length l) | l <- group (sort xs) ]

output :: Map.Map String Int
output = histogram ["a","b","a","c","b","b"]
import Control.Arrow
import Data.List
import qualified Data.Map as Map
import System.Random

histogram :: Ord a => [a] -> Map.Map a Int
histogram = Map.fromList . map (head &&& length) . group . sort

main = print . histogram . take 1000 . randomRs (1::Int, 100) =<< newStdGen
fantom
list := ["a","b","a","c","b","b"]
map := [Str:Int][:]
list.each |Str s, Int i| { if(!map.containsKey(s)) map.add(s,1); else map[s] = ++map[s] }
echo (map)
erlang
% Imperative Solution
Histogram = histogram(List),
% Functional (1) Solution
Histogram = histogram(List),
lists:foldl(fun(Elem, OldDict) ->
dict:update_counter(Elem, 1, OldDict)
end,
dict:new(),
[a,b,a,c,b,b])).

Categorise a list

Given the list [one, two, three, four, five] produce a map {3:[one, two], 4:[four, five], 5:[three]} which sorts elements into map entries based on their length
haskell
import qualified Data.Map as Map

groupInMapBy :: Ord k => (a -> k) -> [a] -> Map.Map k [a]
groupInMapBy f = foldr (\a -> Map.insertWith (++) (f a) [a]) Map.empty

output :: Map.Map Int [String]
output = groupInMapBy length ["one", "two", "three", "four", "five"]
import Data.List (groupBy, sortBy)
import Data.Function (on)

groupInPairsBy :: Ord k => (a -> k) -> [a] -> [(k, [a])]
groupInPairsBy f = map (\xs -> (f (head xs), xs)) .
groupBy ((==) `on` f) . sortBy (compare `on` f)

output :: [(Int, [String])]
output = groupInPairsBy length ["one", "two", "three", "four", "five"]
fantom
list := ["one", "two", "three", "four", "five"]
map := [Int:List][:]
list.each { List l := map[it.size] ?: [,]; map[it.size] = l.add(it) }
echo(map)
erlang
% Imperative Solution
CatList = categorise(List),
% Functional (1) Solution
CatList = categorise(List),