Haskell List Comprehensions

Question

I'm attempting to do a haskell question as I'm trying to learn Haskell.

The question gives me the following type definitions:
type Word = String
type Line = [Word]
type Book = [Line]

The question then asks me to define a function index :: Word -> Book -> [Int] which takes a word and a book, and returns the line numbers the words appear on. eg:
index "example" [["example", "town"], ["example", "cat", "this"]] = [1,2]

So far I have used zip book [1 .. length book] to attach the line numbers to each line, so that would give me

[(["example","town"],1),(["example","cat","this"],2)]

How would I then extract only the line numbers? I am assuming I would use list comprehensions but I'm not sure how to do it.

Answer 1

The general list comprehensions scheme for these things is

g xs = [i | (x,i) <- zip xs [1..], pred x]

pred is a predicate acting on elements of xs, the input list; only for those that pass the test, their original indices are included in the output. Of course this can be done with higher order functions, as

g xs = map snd . filter (pred . fst) . (`zip` [1..]) $ xs

(.) is the function composition operator: pred . fst == (\p -> pred (fst p)). Thus the above line could also be written

g xs = map snd . filter (\(x,i) -> pred x) . (`zip` [1..]) $ xs

whatever is more readable to you.

update: filter is also implementable as

filter pred = concatMap (\x -> [x | pred x])

so the mapping can be fused in, giving us

g :: (a -> Bool) -> [a] -> [Int]
g pred = concatMap (\(x,i) -> [i | pred x]) . (`zip` [1..])

concatMap can also be replaced with foldMap, join . map ... and even asum . map ....

Answer 2

As mentioned in others posts you can use the zip function to decorate each line with a line number. You can then use a list comprehension to search through:

search :: Word -> Book -> [Int]  
search w b =  
  [n | (line, n) <- lines, elem w line]  
  where lines = zip b [1..]

You can also define the the function using foldl (not sure it's good style though, I am still a beginner in Haskell):

search :: Word -> Book -> [Int]
search w b =
  fst $ foldl foo ([], 1) b
  where foo (rs, n) line | elem w line = (n : rs, n+1)
                         | otherwise = (rs, n+1)

You could also define this recursively, etc. Hope it helped!

Answer 3

You could use map, which applies a function to every element in a list. The function you want to apply is snd, which extracts the second element.

λ> let xs = [(["example","town"],1),(["example","cat","this"],2)]
λ> map snd xs
[1,2]

You might want to show us the rest of your code. You mentioned that you used Tzip book [1 .. length book] -- there are usually easier and more efficient ways than using the length function. We might be able to suggest a more "Haskellish" way of doing it.

Edit: filtering

We can filter the list by writing a simple function to find all of the entries that contain the word we're interested in. In the example below, I've defined containsWord for this purpose:

λ> let xs = [(["example","town"],1),(["example","cat","this"],2)]
λ> let containsWord w (ws,_) = w `elem` ws
λ> let ys = filter (containsWord "cat") xs
λ> map snd ys
[2]

Or, if you want to define the function inline:

λ> let xs = [(["example","town"],1),(["example","cat","this"],2)]
λ> let ys = filter (\(zs,_) -> "cat" `elem` zs) xs
λ> map snd ys
[2]

You can of course use list comprehensions for all this stuff. But you may find that using functions like map and filter result in more readable code. If you look back at your code a few months from now, you'll immediately understand the purpose of map and filter, but it takes closer inspection to figure out what a list comprehension is actually doing. I prefer to use list comprehensions only for situations that aren't already covered by familiar functions.