Make Haskell List Recursion function more efficient

Question

I've written a function that will compare two lists and check to see if the first is a prefix of the second and it must be done using recursion.

For example:

prefix [1,2] [1,2,3]
>True
prefix [2,1,4] [2,1,13,4]
>False

Now I've done this but I feel it's inefficient:

prefix :: [Int] -> [Int] -> Bool
prefix (x:xs) (y:ys)
|   null xs                         =   True
|   x == y && head xs == head ys    =   True && prefix xs ys
|   head xs /= head ys              =   False

I was hoping it could be done more efficiently and with some better pattern matching. Can it be?

A good way to catch missing patterns is to run GHC with -fwarn-incomplete-patterns or just -Wall. Typically, write {-# OPTIONS_GHC -Wall #-} way up at the top of the file. — dfeuer
– dfeuer, Commented Jan 28, 2016 at 21:03

Chad Gilbert · Accepted Answer · 2016-01-28 19:50:00Z

5

You don't need to use the head function at all. That doubles the number of comparisons. Try this:

prefix :: [Int] -> [Int] -> Bool
prefix [] _ = True
prefix _ [] = False
prefix (x:xs) (y:ys)
  | x == y = prefix xs ys
  | otherwise = False

edited Jan 28, 2016 at 19:50

answered Jan 28, 2016 at 18:32

Chad Gilbert

36.4k4 gold badges93 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

GarethAS Over a year ago

Oh I see, yes that does work and I've now found an instance in which mine doesn't, when I make the first list contain any single integer it will return true. Can you explain the (_:_) part of your solution?

Chad Gilbert Over a year ago

(_:_) [] matches the case when the first list is longer than the second, meaning the first could never be a prefix of the second. (the code could actually be shortened to _ [] since we've already matched on an empty first list in the first pattern)

mb21 Over a year ago

@GarethAllen-Stringer (x:xs) in that case pattern-matches on the first item of the list (x) and the tail (xs), see learnyouahaskell.com/syntax-in-functions

dfeuer · Accepted Answer · 2016-01-28 20:22:12Z

2

Chad Gilbert's solution can be streamlined very slightly:

prefix :: [Int] -> [Int] -> Bool
prefix [] _ = True
prefix (x:xs) (y:ys)
  | x == y = prefix xs ys
prefix _ _ = False

This won't affect the performance, but it demonstrates a language feature: when all the guards on a pattern fail, that match will be abandoned and matching will resume with the next pattern.

answered Jan 28, 2016 at 20:22

dfeuer

48.8k5 gold badges69 silver badges171 bronze badges

Comments

Zacharie 007 · Accepted Answer · 2016-01-28 20:46:59Z

0

 Prelude > let prefix [] _ = True
 Prelude |     prefix _ [] = False
 Prelude |     prefix (x:xs) (y:ys) = if ( x==y) then prefix xs ys else False

Examples:

  Prelude> prefix [1,3] []
  False
  Prelude> prefix [] [1,2,3]
  True
  Prelude> prefix [1,2] [1,2,3]
  True

answered Jan 28, 2016 at 20:46

Zacharie 007

1264 bronze badges

Collectives™ on Stack Overflow

Make Haskell List Recursion function more efficient

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related