Pattern-match list of tuple Strings

Question

So I have a lost of String tuples in Haskell. I declared a type for that:

type Book = [(String, String)]

Then I declared an empty book:

emptyBook :: Book
emptyBook = []

And now I want to create a function that inserts elements to a book. My solution:

insert :: String -> String -> Book -> Book
insert a b emptyBook = (a,b) : []
insert a b (x : xs)= (a, b) : (x:xs)

But the function insert is not working. The compiler loads the module but gives the warning 'Pattern match is redundant'.

Executing insert "a" "1" [("b","2")] gives [("a","1")] instead of [("a","1"),("b","2")]

Do you know whats going wrong here?

Answer 1

The clause

insert a b emptyBook = (a,b) : []

defines insert as a function of three general arguments a, b and emptyBook. Well, the last isn't actually used, but that makes no difference – that clause will succeed, no matter what arguments you pass in.

The third argument also shadows the top-level definition emptyBook – basically this makes it so that within the scope of the function, emptyBook is now whatever book you pass in, no matter whether it's empty.

GHC can actually give a warning highlighting this real problem with your code, if you tell it to give generous warnings:

sagemuej@sagemuej-X302LA:~$ runhaskell -Wall /tmp/wtmpf-file2776.hs 

/tmp/wtmpf-file2776.hs:7:12: Warning:
    This binding for ‘emptyBook’ shadows the existing binding
      defined at /tmp/wtmpf-file2776.hs:4:1

/tmp/wtmpf-file2776.hs:7:12: Warning:
    Defined but not used: ‘emptyBook’

If you want emptyBook to be a constant that should be matched on, you have to make it explicit that this is not a newly-bound argument variable. A couple of options:

• (Not recommended) use equality comparison instead of pattern matching

  insert a b book
    | book==emptyBook  = (a,b) : []
  insert a b (x : xs)  = (a, b) : (x:xs)
  

  We generally avoid equality comparison in Haskell – it's less general, less efficient and more error-prone than pattern matching.

• (Very not recommended) use a C-preprocessor macro (Template Haskell would also work) to actually insert literally [] in that pattern matching. You can't have a variable named [], so this will do the right thing:

  {-# LANGUAGE CPP #-}
  
  #define emptyBook []
  
  insert :: String -> String -> Book -> Book
  insert a b emptyBook = (a,b) : []
  insert a b (x : xs) = (a, b) : (x:xs)
  

  Such macro definitions don't work very well with Haskell – they're completely oblivious of the languages scopes, can't be exported etc..

• (Not very recommended) use pattern synonyms. Those are essentially the modern, Haskell-native way of achieving the behaviour I did above with a CPP macro:

  {-# LANGUAGE PatternSynonyms #-}
  
  pattern EmptyBook :: Book
  pattern EmptyBook = []
  
  insert :: String -> String -> Book -> Book
  insert a b emptyBook = (a,b) : []
  insert a b (x : xs) = (a, b) : (x:xs)
  

So, what would be the recommended solution? Well, as Willem Van Onsem says, you just don't need that clause at all – it's already a special case of the second clause!

insert :: String -> String -> Book -> Book
insert a b (x : xs) = (a, b) : (x:xs)

...which is the same as

insert a b (x : xs) = (a, b) : x : xs

or

insert a b xxs = (a, b) : xxs

or

insert a b = ((a, b) :)

or

import Data.Function.Pointless

insert=(:).:(,)

Answer 2

I don't get why you:

1. use emptybook in your pattern matching part, instead of [];
2. why you repeat (x:xs) both in the left and in the right part of the expression;
3. make a distinction between an empty book and a non-empty book.

Why it doesn't work

Because Haskell, like many other languages uses variable scopes, and Haskell sees emptybook in your function as a variable. It does not see (at least not there) that emptybook is a function somewhere defined. So could have written:

insert a b c = (a,b) : []

as well (as second line in your function definition). Now since you define a variable c and did not put any constraints (guards, patterns,...) on it, it matches with everything: so a non-empty book as well. Therefore Haskell will always take the first line. In fact the compiler already warns you for this. It says:

haskell.hs:9:1: Warning:
    Pattern match(es) are overlapped
    In an equation for ‘insert’: insert a b (x : xs) = ...

This means that the last line of your function definition overlaps with the previous lines. In that case you have probably done something wrong.

Alternative

You can simply use:

insert :: String -> String -> book -> book
insert a b xs = (a,b) : xs

or even shorter:

insert :: String -> String -> book -> book
insert a b = (:) (a,b)

Furthermore types are usually denoted with a capital letter, so you better use Book instead of book.