Haskell: List Comprehension to Combinatory

问题:

Inspired by this article. I was playing with translating functions from list comprehension to combinatory style. I found something interesting.

-- Example 1: List Comprehension 
*Main> [x|(x:_)<-["hi","hello",""]]
"hh"

-- Example 2: Combinatory
*Main> map head ["hi","hello",""]
"hh*** Exception: Prelude.head: empty list

-- Example 3: List Comprehension (translated from Example 2)
*Main> [head xs|xs<-["hi","hello",""]]
"hh*** Exception: Prelude.head: empty list 

It seems strange that example 1 does not throw an exception, because (x:_) pattern matches one of the definitions of head. Is there an implied filter (not . null) when using list comprehensions?

回答1:

See the section on list comprehensions in the Haskell report. So basically

[x|(x:_)<-["hi","hello",""]]

is translated as

let ok (x:_) = [ x ]
    ok _     = [ ]
in concatMap ok ["hi","hello",""]

P.S. Since list comprehensions can be translated into do expressions, a similar thing happens with do expressions, as detailed in the section on do expressions. So the following will also produce the same result:

do (x:_)<-["hi","hello",""]
   return x

回答2:

Pattern match failures are handled specially in list comprehensions. In case the pattern fails to match, the element is dropped. Hence you just get "hh" but nothing for the third list element, since the element doesn't match the pattern.

This is due to the definition of the fail function which is called by the list comprehension in case a pattern fails to match some element:

fail _ = []

The correct parts of this answer are courtesy of kmc of #haskell fame. All the errors are mine, don't blame him.

回答3:

Yes. When you qualify a list comprehension by pattern matching, the values which don't match are filtered out, getting rid of the empty list in your Example 1. In Example 3, the empty list matches the pattern xs so is not filtered, then head xs fails. The point of pattern matching is the safe combination of constructor discrimination with component selection!

You can achieve the same dubious effect with an irrefutable pattern, lazily performing the selection without the discrimination.

Prelude> [x|(~(x:_))<-["hi","hello",""]]
"hh*** Exception: <interactive>:1:0-30: Irrefutable pattern failed for pattern (x : _)

List comprehensions neatly package uses of map, concat, and thus filter.