I was trying to search through a list of pairs that could have the element ("$", Undefined) in it at some arbitrary location. I wanted to ONLY search the part of the list in front of that special element, so I tried something like this (alreadyThere is intended to take the element n and the list xs as arguments):
checkNotSameScope :: Env -> VarName -> Expr -> Expr checkNotSameScope (xs:("$", Undefined):_) n e = if alreadyThere n xs then BoolLit False else BoolLit True
But that does not work; the compiler seemed to indicate that (xs: ..) only deals with a SINGLE value prepending my list. I cannot use : to indicate the first chunk of a list; only a single element. Looking back, this makes sense; otherwise, how would the compiler know what to do? Adding an "s" to something like "x" doesn't magically make multiple elements! But how can I work around this?Answer1:
Unfortunately, even with smart compilers and languages, some programming cannot be avoided...
In your case it seems you want the part of a list up to a specific element. More generally, to find the list up to some condition you can use the standard library
takeWhile function. Then you can just run
alreadyThere on it:
checkNotSameScope :: Env -> VarName -> Expr -> Expr checkNotSameScope xs n e = if alreadyThere n (takeWhile (/= ("$", Undefined)) xs) then BoolLit False else BoolLit True
It maybe does not what you want for lists where
("$", Undefined) does not occur, so beware.
Similar to Joachim's answer, you can use <a href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v%3abreak" rel="nofollow">
break</a>, which will allow you to detect when
("$", Undefined) doesn't occur (if this is necessary). i.e.
checkNotSameScope xs n e = case break (== ("$", Undefined)) xs of (_, ) -> .. -- ("$", Undefined) didn't occur! (xs', _) -> BoolLit . not $ alreadyThere n xs'
(NB. you lose some laziness in this solution, since the list has to be traversed until
("$", Undefined), or to the end, to check the first case.)
Haskell cannot do this kind of pattern matching out of the box, although there are some languages which can, like <a href="http://en.wikipedia.org/wiki/CLIPS" rel="nofollow">CLIPS</a> for example, or F#, by using <a href="http://msdn.microsoft.com/en-us/library/dd233248.aspx" rel="nofollow">active patterns</a>.
But we can use Haskell's existing pattern matching capabilities to obtain a similar result. Let us first define a function called deconstruct defined like this:
deconstruct :: [a] -> [([a], a, [a])] deconstruct  =  deconstruct [x] = [(, x, )] deconstruct (x:xs) = (, x, xs) : [(x:ys1, y, ys2) | (ys1, y, ys2) <- deconstruct xs]
What this function does is to obtain all the decompositions of a list xs into triples of form
(ys1, y, ys2) such that
ys1 ++ [y] ++ ys2 == xs. So for example:
deconstruct [1..4] => [(,1,[2,3,4]),(,2,[3,4]),([1,2],3,),([1,2,3],4,)]
Using this you can define your function as follows:
checkNotSameScope xs n e = case [ys | (ys, ("$", Undefined), _) <- deconstruct xs] of [ys] -> BoolLit $ not $ alreadyThere n xs _ -> -- handle the case when ("$", Undefined) doesn't occur at all or more than once
We can use the <a href="http://www.haskell.org/haskellwiki/Monad#Special_notation" rel="nofollow">do-notation</a> to obtain something even closer to what you are looking for:
checkNotSameScope xs n e = BoolLit $ not $ any (alreadyThere n) prefixes where prefixes = do (xs, ("$", Undefined), _) <- deconstruct xs return xs
There are several things going on here. First of all the
prefixes variable will store all the prefix lists which occur before the
("$", Undefined) pair - or none if the pair is not in the input list
xs. Then using the <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3aany" rel="nofollow">any</a> function we are checking whether
alreadyThere n gives us True for any of the prefixes. And the rest is to complete your function's logic.