Re[2]: [Haskell-cafe] Text search
Hello Gracjan, Monday, May 16, 2005, 4:00:33 PM, you wrote: GP Unless you have very repetitive data and/or tiny alphabet, it is GP actually quite efficient, as the expected length of prefixes that need GP to be checked before a mismatch can be determined is small. GP GP At least, I was unable to beat it with my (feeble attempts at) BM or GP KMP implementations. if you really need KMP, you can find it at http://haskell.org/hawiki/RunTimeCompilation find (isSuffixOf needle) (inits haystack) find (isPrefixOf needle) (tails haystack) if you need an index - add it with zip: find (isPrefixOf needle.snd) (zip [0..] (tails haystack)) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Re[2]: [Haskell-cafe] Text search
From: Bulat Ziganshin [mailto:[EMAIL PROTECTED] if you really need KMP, you can find it at http://haskell.org/hawiki/RunTimeCompilation find (isSuffixOf needle) (inits haystack) find (isPrefixOf needle) (tails haystack) if you need an index - add it with zip: find (isPrefixOf needle.snd) (zip [0..] (tails haystack)) Or: findIndex (isPrefixOf bla) (tails dfvbdbblaesre) (I asked for something similar a few weeks ago: http://www.haskell.org//pipermail/haskell-cafe/2005-April/009690.html ) - * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Unexported functions are evil
Thanks for your opinions everybody! Ketil Malde writes: I guess you could sometimes have name clashes as well? I was afraid about those for the longest time too, but in practice name clashes curiously enough hardly ever occur -- in my experience. The problem only arises when you actually _use_ a function that's ambiguous, just importing two modules with a function called 'foo' in them is no problem. And then you still have the option of using 'hide' or 'qualified' when importing the modules. On those occasions, however, why not put the function into a module, say Foo.Bar.Private and import it into Foo.Bar from there? So you don't want to automatically re-export imports, I take it? :-) No. ;-) Although I would like to have a shortcut for saying (re-)export everything. David Roundy writes: [...] why not put the function into a module, say Foo.Bar.Private and import it into Foo.Bar from there? Because a separate module is more work. It sure is, but I don't think that it's more work or it's less work is a good principle by which to make software design decisions. If you follow this idea through, then you could also argue that splitting a program into separate functions is more work than writing one big, big 'main' function for the task. And it sure is. Still enlightened programmers do just that, because it often turns out that doing so is _less work_ in the long run. I believe the same applies to cleanly grouping functions into separate modules, and a separation between public API and internal implementation doesn't sound so unreasonable, IMHO. Almost every module I write has private functions, and I'd really not want to write twice as many modules. Why do these functions need to be private? In darcs, if someone needs to play with fire, he can do it right there in the module itself, and export a new interface function. Not really, unless you decide to include the patches into the main distribution. If you don't, someone who wants to access the internals essentially has to create a fork of your software, and that's something you really want to avoid if you want to encourage re-use. In the case of darcs, I'd say that the whole point of using modules (besides making things faster to compile) is to place these barriers, so that one can modify an individual module without worrying about the rest of the code, as long as one keeps the interface fixed. I'm not sure whether I understand that. When modifying a function 'foo', why do you have to worry _less_ about 'bar' if it is in a separate module than you'd have to if it would be in the same module? There's also the ease of bug-writing issue. I think that exported interfaces should be the sorts of functions where the meaning of the function can be guessed from its name and type. Shouldn't _any_ function have those properties if at all possible? ajb writes: Is there any reason why you would have a function in one of your modules and _not_ export it? Because that function is nobody else's business. I'm sorry, but that's not really a convincing technical argument, that's essentially because I want it so. So while I think you've identified a real problem (the modules that you want to use expose insufficient APIs), I think your solution is wrong. The right solution is to complain to the module writer, and ask them to export a functionally complete API. So my solution is wrong and your solution is right. ;-) Having that out of the way, what are your reasons for this opinion? (Other than that the art of programming says it ought to be this way.) The only reason I could think of is that a function is considered to be internal [...] Right. And I agree with David: This is reason enough. How is an internal function any _more_ internal if you don't export it? How is it less internal if you _do_ export it? Why doesn't the approach -- | /Attention:/ this function is internal and may change -- at random without even so much as shrug. foo = ... suffice? With my business hat on: Every time you expose something for use, you must at the very least document it. I'd recommend documenting _all_ functions I write, not just the exported ones. Taking this to an illogcial extreme, why don't we allow pointer arithmetic in Haskell, but require people to import Prelude.C first, so that people who enjoy playing with fire can do it? You mean Foreign.Ptr? Curiously enough, if Haskell wouldn't support pointer arithmetic, the language would be completely useless to me, so I for one don't think that's taking things to the illogical extreme. Iavor Diatchki writes: [...] in practice this is likely to often lead to recursive modules [...] Why is that? My intuition would say that the exact opposite is true: a more fine-grained set of modules is _less_ likely to require recursive modules. But that's just intuition. Do you have an concrete example which illustrates
Re: [Haskell-cafe] Data types and Haskell classes
How would I introduce number classes that are extended with plus and minus infinity? I'd like to have polymorphism over these new classes, something like a signature f :: (Real a, Extended a b) = b - b which clearly is not part of the current syntax, but I hope you get the picture. What are the elegant ways of doing this? How about f :: Real a = Extended a - Extended a Double and Float already include -Infinity and +Infinity: Prelude -(1/0) :: Double -Infinity Not quite what I had in mind. I'd like to have extended integers and extended rationals, and possibly extended dyadic numbers. So I can't have just a single type ExtendedRational (unless I'm prepared to do some ugly coersing). Jens ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Text search
On 2005 May 16 Monday 08:00, Gracjan Polak wrote: Ketil Malde wrote: While the result isn't exactly the same, I suspect using isPrefixOf and tails would be more efficient. I need the data before and including my needle. When the haystack gets large, the beautiful find (isSuffixOf needle) (inits haystack) is quite inefficient where it uses isSuffixOf searching longer and longer strings. You can get efficiency, the desired data, and deal with infinite strings by using a function that is like 'inits' but which returns the initial strings in reversed order. reversed_inits = scanl (flip (:)) find (isPrefixOf (reverse needle)) (reversed_inits haystack) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RE: Haskell-Cafe Digest, Vol 21, Issue 31
Date: Wed, 11 May 2005 17:22:25 -0400 (Eastern Standard Time) From: S. Alexander Jacobson [EMAIL PROTECTED] Subject: [Haskell-cafe] subRegex bug? Am I misunderstanding the regex docs? *MyMod subRegex (mkRegex \\. ) foo.bar blah foo*** Exception: Text.Regex.Posix.regcomp: error in pattern Under my Linux install, with ghc6.4, it doesn't throw an exception, but also doesn't return a correct result; it returns Just []. Under WindowsXP, ghc6.4, I get the exception you get; under hugs, it can't find subRegex, but matchRegex returns Just []. What does seem to work is import Text.Regex.Posix p1 = do r - regcomp \\. 0 b - regexec r foo.bar putStr (show b) why it's in the IO monad, I don't know. Where would I find the source? I browsed the ghc cvs at haskell.org, but can't find Text.Regex. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] RE: Haskell-Cafe Digest, Vol 21, Issue 31
From: Atwood, John Wesley [mailto:[EMAIL PROTECTED] Under my Linux install, with ghc6.4, it doesn't throw an exception, but also doesn't return a correct result; it returns Just []. Under WindowsXP, ghc6.4, I get the exception you get; under hugs, it can't find subRegex, but matchRegex returns Just []. What does seem to work is import Text.Regex.Posix p1 = do r - regcomp \\. 0 b - regexec r foo.bar putStr (show b) why it's in the IO monad, I don't know. Where would I find the source? I browsed the ghc cvs at haskell.org, but can't find Text.Regex. John http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/Text/Regex. hs?rev=1.15 - * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Text search
You can get efficiency, the desired data, and deal with infinite strings by using a function that is like 'inits' but which returns the initial strings in reversed order. reversed_inits = scanl (flip (:)) find (isPrefixOf (reverse needle)) (reversed_inits haystack) If I may ask for curiosity's sake, how much string data are we talking about here? Is it practical to process a serious volume of data as [Char]? Donn Cave, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Unexported functions are evil
Hello, On 17 May 2005 12:09:35 +0200, Peter Simons [EMAIL PROTECTED] wrote: Iavor Diatchki writes: [...] in practice this is likely to often lead to recursive modules [...] Why is that? My intuition would say that the exact opposite is true: a more fine-grained set of modules is _less_ likely to require recursive modules. But that's just intuition. Do you have an concrete example which illustrates this point? The smaller the modules are the more likely it is that they will end up being recursive. To see that, consider the extreme where every function is in a separate module, then all recursive groups of functions will end up being recursive groups of modules. As a more practical example consider a file A.hs that defines some data type T and exports a function f that is defined in terms of a private function g. Now if we place g in a file called Private.hs then A needs to import Private, but also Private needs to import A for the definition of T. -iavor ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Bit fiddling
I'm toying a bit with Haskell and wondering what's the best way to implement bit fiddling. Most of my applications involve serializing and deserializing small blobs (IP packets, for instance), and after browsing the GHC library documentation, I'm not sure which appraoch I should use. That's why I'd appreciate pointers to sample code. Portability beyond GHC is not required. It's not necessary to update blobs, only to parse them, and serialize new ones. And in the beginning, I'd like to write the boilerplate manually. 8-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bit fiddling
Probably you have seen this already, but I thought I'd mention it on the off-chance you missed it: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Bits.html http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Word.html Probably you'll want to think about an IOUArray of Word8, or something similar. Its unclear to me exactly what you mean by bit fiddling, but perhaps this addresses your question. Florian Weimer wrote: I'm toying a bit with Haskell and wondering what's the best way to implement bit fiddling. Most of my applications involve serializing and deserializing small blobs (IP packets, for instance), and after browsing the GHC library documentation, I'm not sure which appraoch I should use. That's why I'd appreciate pointers to sample code. Portability beyond GHC is not required. It's not necessary to update blobs, only to parse them, and serialize new ones. And in the beginning, I'd like to write the boilerplate manually. 8-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bit fiddling
If you want C compatibility, you need http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.Storable.html which is similar. You then use the withStorableArray to call out to your C functions. Florian Weimer wrote: * robert dockins: Probably you have seen this already, but I thought I'd mention it on the off-chance you missed it: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Bits.html http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Word.html Probably you'll want to think about an IOUArray of Word8, or something similar. IOUArray looks indeed interesting, thanks. How can I pass such objects (in particular of type IOUArray Int Word8) to a C routine, preferably as a void */size_t combination? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Text search
On 2005 May 17 Tuesday 11:44, Donn Cave wrote: You can get efficiency, the desired data, and deal with infinite strings. reversed_inits = scanl (flip (:)) find (isPrefixOf (reverse needle)) (reversed_inits haystack) With get efficiency, I was comparing this program which is linear time and constant space in the amount of the haystack searched, to an earlier suggestion which was quadratic time and linear space. Is it practical to process a serious volume of data as [Char]? As for your question, GHC _can_ handle a serious volume of [Char]. I don't know how competitive the efficiency is. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bit fiddling
* robert dockins: If you want C compatibility, you need http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.Storable.html which is similar. You then use the withStorableArray to call out to your C functions. Looks exactly like what I need. I'll give it a try and come back if I can't figure out how things fit together. Thanks again. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Bit fiddling
Hi, Florian Weimer wrote: I'm toying a bit with Haskell and wondering what's the best way to implement bit fiddling. Most of my applications involve serializing and deserializing small blobs (IP packets, for instance), and after browsing the GHC library documentation, I'm not sure which appraoch I should use. That's why I'd appreciate pointers to sample code. In the protocol stack in House [1], I have used parsing/unparsing combinators to (de)serialize network packets. This allows the code to be simple, pure and modular, even though you are dealing with data down to the bit level. The way things work at the moment, the network device driver returns incoming packets as unboxed arrays of bytes (values of type UArray Int Word8), and the parsing combinators maintain these along with position information down to the bit level, allowing you to parse input bit by bit. The process is reversed in the unparsing combinators. (What would be nice to have for this is efficient library functions for manipulation of bit vectors of arbitrary dynamic size...) The source code is available on the web, see for example modules Net.Ethernet, Net.ARP, Net.ICMP, Net.IPv4: http://www.cse.ogi.edu/~hallgren/House/kernel/#Net Note though that this is work in progress, there is not much documentation, and the code for several of the protocols is incomplete. -- Thomas H [1] http://www.cse.ogi.edu/~hallgren/House/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell-related Job Posting, Portland OR area
Galois Connections does most of its development in Haskell, and this job may involve some Haskell development, so I felt it was on topic for this list. Senior Test Engineer Galois Connections, Inc., located near Portland, Oregon, designs and develops high confidence software for critical applications using cutting edge methods and technology. Innovative and highly creative problem-solving in the demanding application areas of security, information assurance and cryptography has earned Galois a reputation of excellence in both private and government sectors. Are you seeking an intellectually challenging position in which you'll own a mission-critical piece of a mission-critical product? Do you aspire to work with a team that shares your level of commitment and enthusiasm to develop tomorrow's high-assurance technology today? If so, you might be just the person we're looking for. Galois has recently opened a position for a Senior Test Engineer who will have end-to-end responsibility for the QA process, including planning, QA infrastructure, and assessments. This person will work in a highly cooperative and collaborative team setting and will be responsible for ensuring that our high-assurance projects deliver robust and fully functional systems according to client expectations and potential certifying agencies. For more details about this exciting opportunity please go to: http://www.galois.com/job_testengineer.php To learn more about Galois visit our website at http://www.galois.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Unexported functions are evil
Iavor Diatchki writes: Do you have an concrete example which illustrates this point? [...] consider a file A.hs that defines some data type T and exports a function f that is defined in terms of a private function g. Now if we place g in a file called Private.hs then A needs to import Private, but also Private needs to import A for the definition of T. Ah, now it see it! Great example. But couldn't you just put T in Foo/Base.hs, g in Foo/Private.hs, then create Foo/API.hs which imports Foo/Base.hs and Foo/Private.hs, and leave f in A.hs and import Foo/API.hs? Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe