CODEWITHSUNDEEP
haskell
Kevin Meredith
Kevin Meredith

Reputation: 41909

Pattern Match on First and Last Items of List

Is it possible to pattern match on "starts with f", then any text, and "ends with b?

I tried:

f :: String -> Bool
f ('f':xs:'b') = True
f _            = False

But I got an error:

explore/PatternMatching.hs:2:11:
    Couldn't match expected type ‘[Char]’ with actual type ‘Char’
    In the pattern: 'b'
    In the pattern: xs : 'b'
    In the pattern: 'f' : xs : 'b'
Failed, modules loaded: none.

Upvotes: 3

Views: 1574

Answers (6)

Animesh Saxena
Animesh Saxena

Reputation: 449

To understand the error simply check the signature of : operator

Prelude> :t (:)
(:) :: a -> [a] -> [a]

It can accept an element and a list to give the appended list. When you supply 'f':xs:'b', then it doesn't match the function call.

Upvotes: 0

gallais
gallais

Reputation: 12093

For a list-like data-structure allowing you to access both its first and last element in constant time, you may want to have a look at Hinze and Paterson's fingertrees.

They are shipped by e.g. containers and here are the relevant views to deconstruct them. You may want to write your own view combining deconstruction on the left and the right if you are using this pattern a lot:

data ViewLR a = EmptyLR | SingleLR a | BothSides a (Seq a) a

viewlr :: Seq a -> ViewLR a
viewlr seq =
  case viewl seq of
    EmptyL     -> EmptyLR
    hd :< rest ->
      case viewr rest of
        EmptyR       -> SingleLR hd
        middle :> tl -> BothSides hd middle tl

You may also want to read up on View Patterns to be able to "pattern match" on the left rather than having to use case ... of.

Upvotes: 1

elm
elm

Reputation: 20405

Define a dedicated String data type and hence a form of pattern matching, for instance consider

data HString = Ends Char Char | Plain String 
  deriving (Show, Eq)

Thus

f :: HString -> Bool
f (Ends h l) = (h,l) == ('f','b')
f (Plain "") = False
f (Plain xs) = f $ Ends (head xs) (last xs)

and so

*Main> f (Plain "")
False
*Main> f (Plain "fabs")
False
*Main> f (Plain "fab")
True

Update

Similarly, consider the use of an infix operator :-: to denote a constructor, e.g

infixr 5 :-:

data HString = Char :-: Char | Plain String 
  deriving (Show, Eq)

and thus 

f :: HString -> Bool
f (h :-: l)  = (h,l) == ('f','b')
f (Plain "") = False
f (Plain xs) = f $ (head xs) :-: (last xs)

Upvotes: 0

Chad Groft
Chad Groft

Reputation: 380

As the previous answers state, there's no way to pattern-match directly for this. One might implement it as follows:

f 'f':xs@(_:_) = last xs == 'b'  -- @(_:_) ensures nonempty tail
f _            = False

Upvotes: 2

n. m. could be an AI
n. m. could be an AI

Reputation: 119847

No, it is not possible directly.

: wants a list element on the left side, and a list on the right side.

'f':xs:'b' is invalid because there's something that is not a list on the right side of the second :.

'f':xs:"b" would be valid but won't do what you want, because xs is inferred to be a list element, not a list.

I would do this:

f s = f' (s, reverse s) where
   f' ('f':_, 'b':_) = True
   f' _              = False

Testing:

*Main> f ""
False
*Main> f "f"
False
*Main> f "b"
False
*Main> f "fb"
True
*Main> f "feeeeeeeb"
True
*Main> f (repeat 'b')
False
*Main> f (repeat 'f')
(hangs indefinitely)

Upvotes: 1

ely
ely

Reputation: 77404

There is no easy way to do this without pattern matching language extensions. I would write it as:

f :: String -> Bool
f str = case (take 1 str, drop (length str - 1) str) of
    ("f", "b") -> True
    otherwise -> False

(Using take and drop to avoid specially handling case of an empty string that might cause an error when using e.g. head or !!) 

Prelude> f "flub"
True
Prelude> f "foo"
False
Prelude> f "fb"
True
Prelude> f "fbbbb"
True
Prelude> f "fbbbbf"
False
Prelude> f ""
False

Upvotes: 7

Related Questions