Lists, Ranges and Comprehensions

The workhorse data structure

A list [a] holds elements of one type and is a singly linked list built from [] (empty) and : (cons): [1, 2, 3] is 1 : 2 : 3 : []. Prepending with : is O(1); appending with ++ and indexing with !! are O(n). Ranges generate lists: [1 .. 10], [2, 4 .. 20], ['a' .. 'z'], and thanks to laziness, infinite ranges such as [1 ..]. List comprehensions combine generators, filters and local bindings: [x * x | x <- [1 .. 10], even x]. The Prelude and Data.List provide many functions: map, filter, foldr, sum, product, length, reverse, take, drop, takeWhile, zip, zipWith, concat, concatMap, elem, words, unwords, lines, replicate and, from Data.List, sort, sortOn, group, nub, partition and foldl'. Strings are lists of Char, so these functions work on them too. Beware of partial functions like head and tail, which crash on empty lists; prefer pattern matching or safe alternatives such as Data.List.uncons.

A list as cons cells

Each cell holds a value and a pointer to the rest; [] ends the list.

Working with lists

Ranges, comprehensions and Data.List.

import Data.List (sortOn, group, sort, partition)
import Data.Ord (Down (..))

evensSquared :: [Int]
evensSquared = [x * x | x <- [1 .. 10], even x]           -- [4,16,36,64,100]

pythagorean :: Int -> [(Int, Int, Int)]
pythagorean n = [(a, b, c) | c <- [1 .. n], b <- [1 .. c], a <- [1 .. b], a * a + b * b == c * c]

wordFrequencies :: String -> [(String, Int)]
wordFrequencies text =
  sortOn (Down . snd) [(head ws, length ws) | ws <- group (sort (words text))]

main :: IO ()
main = do
  print evensSquared
  print (pythagorean 15)                   -- [(3,4,5),(6,8,10),(5,12,13),(9,12,15)]
  print (zip [1 :: Int ..] "abc")          -- [(1,'a'),(2,'b'),(3,'c')]
  print (takeWhile (< 40) (map (^ 2) [1 :: Int ..]))   -- [1,4,9,16,25,36]
  print (partition even [1 .. 10 :: Int])  -- ([2,4,6,8,10],[1,3,5,7,9])
  print (wordFrequencies "to be or not to be")
  -- [("be",2),("to",2),("not",1),("or",1)]

head is safe only when you know the list is non-empty

In wordFrequencies, group never produces empty groups, so head ws is safe. Elsewhere, match on (x : _) or use Data.List.NonEmpty so the type guarantees non-emptiness.

त्वरित जाँच: What is the cost of prepending an element to a Haskell list with (:)?

• O(n)
• O(log n)
• O(1)
• O(n squared)