Clever Geek Handbook

Haskell: Is there an identifier on the left for the infix operator (`:`)?

In other words, what syntax (if any) I could use instead XXX

in the following filter implementation:

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []     = []
filter' f (x:xs) =
  let n = if f x then x else XXX
  in  n:(filter' f xs)

I know the following alternative implementation (which is recursive and only adds), but would still be curious if the infix operator has an LHS identity.

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []     = []
filter' f (x:xs)
  | f x = x:(filter' f xs)
  | otherwise = filter' f xs
+3


source to share


3 answers


Not. This can be seen because

ghci> length (undefined : [])
1

so no matter what element you put there you will always have a length of 1.



How about this phrase:

filter' f (x:xs) =
    let n = if f x then (x:) else id
    in  n (filter' f xs)
+12


source


Manual Worry Warning: Strictly speaking, this is a lie (due to undefined

, etc.), but it's still a useful idea.

One key property of types defined with Haskell declarations data

is that they are free : the set of values ​​for a type data

is isomorphic to the set of normal form terms (fully evaluated expressions) of that type. If two members of a type are different, then they have different meanings.

It follows that x : xs

and xs

(in the same scope) must be different lists, simply because they are different terms.



To put it a little differently, the semantics of the types data

is that if you match templates to a constructor application, you always return the same constructor and its arguments. For example, these two expressions are guaranteed True

, no matter what x

, and xs

can be:

case [] of
    []   -> True
    x:xs -> False

case (x:xs) of
    []     -> False
    x':xs' -> x == x' && xs == xs'

The left identity value you are looking for would be a counterexample to the second expression here. Ergo, there is no such meaning.

+2


source


No, but ++

has an ID, viz []

. So this will work:

filter' _ [] = []
filter' f (x:xs) =
     let n = if f x then [x] else [] 
     in n ++ (filter' f xs)

This is the same as @ luqui's answer (as you could prove) only less efficient, but it keeps things a little lower.

+2


source






More articles:


All Articles