22961

Haskell pattern matching conundrum

Question:

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.

Answer2:

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.)

Answer3:

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]),([1],2,[3,4]),([1,2],3,[4]),([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.

Recommend

  • If I don't explicitly map a column in code-first EF to an existing DB, will that column still w
  • MSI Uninstall issue: Error 1001 -> The saved State dictionary contains inconsistent data and migh
  • Copy all files but change the name of some automatically in yeoman
  • WPF DispatcherFrame magic - how and why this works?
  • Translate OData queries to SQL
  • how to find function boundaries in binary code
  • how to insert data into multiple tables through ItemWriter
  • Split an image into 64x64 chunks
  • Is there a pre-defined built-in function to convert a number to its binary format in C++?
  • Const variable in C++ function body
  • Advantage of 'one dimensional' hash over array in Perl
  • Spacing/Leading PdfPCell's elements
  • Does Microsoft chatbot(Node.js) support multiple language in the single LUIS.AI application?
  • Maven archetype generate with custom properties
  • C# Application Relative Paths
  • Use query params of parent route to refresh the model in subroute
  • How to distribute an event to all nodes in a (Wildfly) cluster?
  • reset jquery smartwizard
  • Flex/AS3 very strange simple Number operation issue
  • SQL query to group by maximal sets of a column having inner consecutive distances below a threshold
  • Why can't I use non-integral types with switch [duplicate]
  • Serve file to user over http via php
  • can variables be set randomly when declaring them again?
  • C# - Most efficient way to iterate through multiple arrays/list
  • Is it possible to open regedit and navigate to straight to a specific key using process.start?
  • Object and struct member access and address offset calculation
  • How to use remove-erase idiom for removing empty vectors in a vector?
  • Cancel a live stream “fast motion” catch-up in Flash
  • Extracting HTML between tags
  • Repeat a vertical line on every page in Report Builder / SSRS
  • Android screen density dpi vs ppi
  • Why HTML5 Canvas with a larger size stretch a drawn line?
  • Bug in WPF DataGrid
  • Why doesn't :active or :focus work on text links in webkit? (safari & chrome)
  • How to add a column to a Pandas dataframe made of arrays of the n-preceding values of another column
  • Knitr HTML Loop - Some HTML output, some R output
  • When should I choose bucket sort over other sorting algorithms?
  • Unanticipated behavior
  • Linker errors when using intrinsic function via function pointer
  • java string with new operator and a literal