Re: [Haskell-cafe] Prettier pretty-printing of data types?
I guess you want an automatically derived show that indents, but if you don't mind defining you own, Data.PrettyPrint is really nice. Here is an example that produces roughly the same as your example: import Data.PrettyPrint tree2doc Leaf = text "Leaf" tree2doc (Bin x l r) = text "Bin" $$ nest 2 (text (show x) $$ tree2doc l $$ tree2doc r) showTree = render . tree2doc /Johan 2012/3/13 Johan Tibell : > Hi all, > > The derived Show instance is useful, but I sometimes wish for > something that's easier to read for big data types. Does anyone have > an implementation of show that draws things in a hierarchical manner? > Example: > > Given > > data Tree a = Leaf | Bin Int a (Tree a) (Tree a) > > and > > value = Bin 1 (Bin 2 Leaf Leaf) (Bin 3 Leaf Leaf) > > draw as > > Bin > 1 > Bin > 2 > Leaf > Leaf > Bin > 3 > Leaf > Leaf > > Cheers, > Johan > > ___ > 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] Why so many strings in Network.URI, System.Posix and similar libraries?
2012/3/12 Jeremy Shaw : > On Sun, Mar 11, 2012 at 1:33 PM, Jason Dusek wrote: >> Well, to quote one example from RFC 3986: >> >> 2.1. Percent-Encoding >> >> A percent-encoding mechanism is used to represent a data octet in a >> component when that octet's corresponding character is outside the >> allowed set or is being used as a delimiter of, or within, the >> component. > > Right. This describes how to convert an octet into a sequence of characters, > since the only thing that can appear in a URI is sequences of characters. > >> The syntax of URIs is a mechanism for describing data octets, >> not Unicode code points. It is at variance to describe URIs in >> terms of Unicode code points. > > > Not sure what you mean by this. As the RFC says, a URI is defined entirely > by the identity of the characters that are used. There is definitely no > single, correct byte sequence for representing a URI. If I give you a > sequence of bytes and tell you it is a URI, the only way to decode it is to > first know what encoding the byte sequence represents.. ascii, utf-16, etc. > Once you have decoded the byte sequence into a sequence of characters, only > then can you parse the URI. Mr. Shaw, Thanks for taking the time to explain all this. It's really helped me to understand a lot of parts of the URI spec a lot better. I have deprecated my module in the latest release http://hackage.haskell.org/package/URLb-0.0.1 because a URL parser working on bytes instead of characters stands out to me now as a confused idea. -- Jason Dusek pgp /// solidsnack 1FD4C6C1 FED18A2B ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] using mutable data structures in pure functions
On Sun, Mar 11, 2012 at 8:38 PM, E R wrote:
> A pure function can allocate and modify memory as long as a) it never
> returns a reference to the memory or b) it never again modifies the
> memory once it returns (i.e. it returns an immutable object).
>
That's a reasonable first approximation to the problem, yes. It gets a bit
more complicated due to laziness (what if the mutation gets delayed until
some later part of the output is examined?)
So, again, what is the Haskell philosophy towards using mutable data
> structures in pure functions? Is it:
>
> 1. leave it to the compiler to find these kinds of opportunities
> 2. just use the immutable data structures - after all they are just as
> good (at least asymptotically)
> 3. you don't want to use mutable data structures because of _
> 4. it does happen, and some examples are __
>
There are two ways in which Haskell encourages the use of mutable data
structures in a pure way.
The first is in the inherent mutation caused by laziness. For example:
type Positive = Integer
-- trie of binary representation of positive number
-- [1] -> tOne
-- x ++ [0] -> lookup x . tEven
-- x ++ [1] -> lookup x . tOdd
data Trie a = Trie {
tOne :: a,
tEven :: NatTrie a,
tOdd :: NatTrie a
}
lookupTrie :: Trie a -> Positive -> a
lookupTrie t 1 = tOne t
lookupTrie t n
| even n = lookupTrie (tEven t) (n `div` 2)
| otherwise = lookupTrie (tOdd t) (n `div` 2) -- div drops remainder
makeTrie :: (Positive -> a) -> Trie a
makeTrie f = Trie (f 1) e o where
e = makeTrie $ \n -> f (2*n)
o = makeTrie $ \n -> f (2*n + 1)
memoize :: (Positive -> a) -> (Positive -> a)
memoize = lookupTrie . makeTrie
collatz_rec :: (Positive -> Integer) -> Positive -> Integer
collatz_rec f 1 = 0
collatz_rec f n
| even n = 1 + f (n `div` 2)
| otherwise = 1 + f (3*n + 1)
collatz = memoize (collatz_rec collatz)
In this case, makeTrie creates a thunk, and it's only evaluated where
requested by lookupTrie. You can call collatz at many different values and
later calls will be much faster, as the mutation caused by lazy evaluation
'remembers' the values.
The second is by explicitly documenting that you are using a temporarily
mutable structure, which is the ST monad:
instance Monad (ST s)
newSTRef :: a -> ST s (STRef s a)
readSTRef :: STRef s a -> ST s a
writeSTRef :: STRef s a -> a -> ST s ()
-- and similar interface for mutable STArrays
runST :: (forall s. ST s a) -> a -- note higher rank type
A computation in the ST monad is an impure computation that can modify
memory, but only memory allocated within that same computation.
The higher rank type in runST makes it safe to do so--references from one
ST computation cannot escape to any other ST computation. So even though
internally some pure value might rely on an impure computation, it's safe
to do so in a pure context.
Here's a sample implementation of ST:
-- DO NOT EXPORT THESE CONSTRUCTORS
newtype ST s a = ST (IO a)
newtype STRef s a = STRef { getRef :: IORef a }
runST :: (forall s. ST s a) -> a
runST (ST act) = unsafePerformIO act -- Actually safe!
newSTRef :: a -> ST s (STRef s a)
newSTRef a = ST $ liftM STRef (newIORef a)
readSTRef :: STRef s a -> ST s a
readSTRef (STRef r) = ST $ readIORef r
writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef (STRef r) a = ST $ writeIORef r a
There's some usage examples at http://www.haskell.org/haskellwiki/Monad/ST
-- ryan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there a better way to subtyping?
Why not
data Super
= SuperA {
commonFields :: ()
aFields :: ()
}
| SuperB {
commonFields :: ()
bFields :: ()
}
| SuperC {
commonFields :: ()
cFields :: ()
}
reusing the common field names between constructors like this is a-okay.
John
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there a better way to subtyping?
data Common = ...
data A = ...
data B = ...
data C = ...
data Super =
SubA { commonFields :: Common, getA :: A }
| SubB { commonFields :: Common, getB :: B }
| SubC { commonFields :: Common, getC :: C }
foldWithSubtype :: (A -> r) -> (B -> r) -> (C -> r) -> Super -> r
foldWithSubtype k _ _ (SubA {getA = a}) = k a
foldWithSubtype _ k _ (SubB {getB = b}) = k b
foldWithSubtype _ _ k (SubC {getC = c}) = k c
foldSuper :: (A -> Common -> r) -> (B -> Common -> r) -> (C -> Common -> r)
-> Super -> r
foldSuper ka kb kc sup = foldWithSubtype ka kb kc sup $ commonFields sup
On Mon, Mar 12, 2012 at 8:32 AM, Jeff Shaw wrote:
> More specifically, if I have a record type from which I construct multiple
> sub-record types, and I want to store these in a collection which I want to
> map over while preserving the ability to get at the sub-fields, is there a
> better way to do it than to have an enumeration for the sub-types and then
> use Dynamic? I also have a nastier version that doesn't require the
> enumeration, which throws an exception when fromDynamic can't return a
> value with one of the expected types.
>
> {-# LANGUAGE Rank2Types, DeriveDataTypeable #-}
> module Super where
>
> import Data.Dynamic
> import Data.Typeable
> import Data.Maybe
>
> data Super a = Super { commonFields :: (), subFields :: a }
>deriving Typeable
>
> data SubTypes = SubA | SubB | SubC
>
> data A = A { aFields :: () }
>deriving Typeable
>
> data B = B { bFields :: () }
>deriving Typeable
>
> data C = C { cFields :: () }
>deriving Typeable
>
> doSomethingWithSubType :: (Super A -> ()) -> (Super B -> ()) -> (Super C
> -> ()) -> (SubTypes, Dynamic) -> Maybe ()
> doSomethingWithSubType a _ _ (SubA, dynamic) = fromDynamic dynamic >>=
> return . a
> doSomethingWithSubType _ b _ (SubB, dynamic) = fromDynamic dynamic >>=
> return . b
> doSomethingWithSubType _ _ c (SubC, dynamic) = fromDynamic dynamic >>=
> return . c
>
> doSomethingWithSubType2 :: (Super A -> ()) -> (Super B -> ()) -> (Super C
> -> ()) -> Dynamic -> ()
> doSomethingWithSubType2 a b c dynamic =
>let dynamicAsA = fromDynamic dynamic :: Maybe (Super A)
>dynamicAsB = fromDynamic dynamic :: Maybe (Super B)
>dynamicAsC = fromDynamic dynamic :: Maybe (Super C) in
>head $ catMaybes [ dynamicAsA >>= return . a
> , dynamicAsB >>= return . b
> , dynamicAsC >>= return . c]
>
>
> __**_
> 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] An idea to document inter department dependencies in Haskell
Hi, Just thinking aloud : A way to start is to define concrete workflows for concrete events. "What It is necessary to do if". This may make things more explicit and to clarify the problems. .Later, .maybe. these concrete workflows can be abstracted away from procedural/imperative to declarative and from concrete events to categories of events and tasks.. The declarative abstract description then could create concrete workflows. The best way to express the abstract description, and the way to transform the description in a concrete set of instructions depend on what is needed (The workflows produced can be just informative, in the form of a textual description of activities). Thus, the power users should handle the abstract descriptions, and the ordinary users could run the engine, perhaps they should answer some questions to obtain the concrete workflows for their intended tasks Not very informative, but better than nothing ;) Alberto 2012/3/13 C K Kashyap > My dear Haskell folks, > > I work in a software company where I develop components that go into a > really complex system that's built of several components developed by > different teams that are geographically distributed. The components > themselves run in a distributed manner across client and several servers. > All our design documents are in wiki's (fashionably so). As a result of the > above situation and the fact that our code base is not in Haskell, we are > almost always dealing with "Oh I did not know this would effect that" and > "Oh I have no clue what all this change will impact". > > I've been wondering if it would be a good idea to try and create a spec > for the system in Haskell, such that would could get a better handle on the > dependencies. Perhaps an EDSL, that would allow Product Managers to > introduce new requirements - compilation failures would indicate the areas > that would need to be touched. How is it different from having a spec in a > diagram - well, in that case, we are requiring humans to look at the > diagram to detect dependencies instead of the compiler telling me about the > dependencies. I am about to start off with some implementation to capture > my idea - I can articulate it better then. However, I just wanted to throw > it out there to check if anyone's had some thought in this direction or if > there is some prior art here. > > Regards, > Kashyap > > > ___ > 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] Prettier pretty-printing of data types?
Maybe an Emacs script to expand the nodes nicely: http://www.youtube.com/watch?v=6ofEZQ7XoEA I don't find mere pretty printing that useful compared to the “expanding” paradigm I'm used to in Chrome and Firebug. To try it just M-x eval-buffer on these two files, http://www.emacswiki.org/emacs/download/peg.el https://raw.github.com/chrisdone/haskell-emacs/master/src/hs-show.el then make some fresh empty buffer with some demo Show output code: BinJab 1 (Biny 2 Leaf Leaf) (Binpo 3 Leaf Leaf) (Binamr 3 Leaf (Lalar 3 Leaf Leaf)) and try, maybe, M-: (hs-show-replace (point-min) (point-max)) you should get “BinJab”, and then clicking it will give you more until you have: http://i.imgur.com/a7rvz.png The parser is of course a PEG parser within elisp so it kind of sucks for large data structures (limited by Elisp's stack, and is super slow). My haskell-emacs package has it in the REPL but I want to replace this parser with a haskell-src-exts→sexp utility to make it faster and more reliable. If anyone wants to replace the parser (and indeed the "shower") as described, I'd be very happy as this is a Super Nice feature and indispensable in the REPL with “real” data. Ciao! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prettier pretty-printing of data types?
I prefer pretty-show rather than groom as it's output is hierarchical. http://hackage.haskell.org/package/pretty-show Ozgur On 13 March 2012 22:37, Austin Seipp wrote: > It's not exactly hierarchical, but Groom most certainly should help > with getting much prettier output: > > http://hackage.haskell.org/package/groom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prettier pretty-printing of data types?
On 03/13/2012 10:33 PM, Johan Tibell wrote: value = Bin 1 (Bin 2 Leaf Leaf) (Bin 3 Leaf Leaf) I'm usually using the following snippet which is a tweak of the gshow function from syb. However everything need to be a member of Data/Typeable, and also list are not particularly well handled with this. gshowHier :: Data a => Int -> a -> String gshowHier il a = intercalate "\n" (constr : gmapQ (gshowHier (il+2)) a) where constr = replicate il ' ' ++ (showConstr $ toConstr a) -- Vincent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prettier pretty-printing of data types?
It's not exactly hierarchical, but Groom most certainly should help with getting much prettier output: http://hackage.haskell.org/package/groom On Tue, Mar 13, 2012 at 5:33 PM, Johan Tibell wrote: > Hi all, > > The derived Show instance is useful, but I sometimes wish for > something that's easier to read for big data types. Does anyone have > an implementation of show that draws things in a hierarchical manner? > Example: > > Given > > data Tree a = Leaf | Bin Int a (Tree a) (Tree a) > > and > > value = Bin 1 (Bin 2 Leaf Leaf) (Bin 3 Leaf Leaf) > > draw as > > Bin > 1 > Bin > 2 > Leaf > Leaf > Bin > 3 > Leaf > Leaf > > Cheers, > Johan > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Regards, Austin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Prettier pretty-printing of data types?
Hi all, The derived Show instance is useful, but I sometimes wish for something that's easier to read for big data types. Does anyone have an implementation of show that draws things in a hierarchical manner? Example: Given data Tree a = Leaf | Bin Int a (Tree a) (Tree a) and value = Bin 1 (Bin 2 Leaf Leaf) (Bin 3 Leaf Leaf) draw as Bin 1 Bin 2 Leaf Leaf Bin 3 Leaf Leaf Cheers, Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic addition function with variable number of arguments?
The problem seems to be that numeric literals are polymorphic. With your code, this works: *Main> let x = 8 :: Int *Main> add x x x :: Int 24 *Main> add x x :: Int 16 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic addition function with variable number of arguments?
I'm sorry this was a typo. Here's the correct one:
{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
class Add a b where
add :: a -> b
instance Num a => Add a a where
add = id
instance (Num a, Add a b) => Add a (a -> b) where
add x y = add (x + y)
I'm trying to use the printf trick to achieve this.
On Tue, Mar 13, 2012 at 9:30 PM, Johannes Waldmann <
waldm...@imn.htwk-leipzig.de> wrote:
> > Can someone tell me why this is not working
>
> that "someone" is actually ghci:
>
> Prelude> instance (Num a, Add a b) => Add (a -> b) where add x y = add (x
> + y)
>
> :8:30:
>Expecting one more argument to `Add (a -> b)'
>In the instance declaration for `Add (a -> b)'
>
>
>
>
> ___
> 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] Polymorphic addition function with variable number of arguments?
> Can someone tell me why this is not working that "someone" is actually ghci: Prelude> instance (Num a, Add a b) => Add (a -> b) where add x y = add (x + y) :8:30: Expecting one more argument to `Add (a -> b)' In the instance declaration for `Add (a -> b)' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Polymorphic addition function with variable number of arguments?
Dear Haskellers, I'm trying to define a polymorphic "add" function which takes a variable number of arguments (instance of Num) and returns their sum. I don't want to specify the types of the arguments while calling the function, I just want to , at most, specify the return type (*it should infer that the return type is the type of the arguments*). class Add a b where add :: a -> b instance Num a => Add a a where add = id instance (Num a, Add a b) => Add (a -> b) where add x y = add (x + y) Can someone tell me why this is not working and propose a fix for this, if possible? Thanks in advance ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Inecxact map?
On Tue, Mar 13, 2012 at 6:14 AM, Holger Siegel wrote: > > Am 13.03.2012 um 09:15 schrieb Morten Olsen Lysgaard: > >> I'd like to be able to do inexact lookups on the map. Firstly, ignore the >> difference between upper lower case, that's easy. But secondly, have a >> function: >> >> search :: (Num b) => Data.Map.Map String a -> String -> b -> [a] >> >> This function is like the normal lookup, but it takes an extra argument b. B >> is the allowed character error rate. That is the Levenstein distance divided >> on the length. It should return all the strings that has an error rate lower >> that b and in a ordered manner, best first. > > You could take a trie and extend the lookup functions so that it also returns > inexact matches up to a given error rate. That should be quite easy, because > the definition of Levenshtein distance is recursive as well as the trie's > lookup function. There are also Burkhard-Keller trees, which are a pretty cool data structure: http://hackage.haskell.org/package/bktrees-0.3.1 --S. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal test-suite library recompilation
On 13 March 2012 16:22, Antoine Latter wrote: > If your library code and test code are in separate sub-directories and > you reference your library as a package dependency for your test then > Cabal won't re-build your library. > Yay! That was it. Thanks. Somehow I altered the hs-source-dir field while moving from the old setup to the new setup. So just to confirm, the behaviour of the test-suite section is exactly the same as that of executable sections. Cheers, Ozgur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] cabal test-suite library recompilation
On Tue, Mar 13, 2012 at 11:16 AM, Ozgur Akgun wrote: > > While waiting for a build to finish [ :) ], I just wanted to write an email > and check if this is intentional or only an oversight. Or maybe a technical > limitation for the time being? > If your library code and test code are in separate sub-directories and you reference your library as a package dependency for your test then Cabal won't re-build your library. That is, the 'Hs-source-disr' for the library and the test should not overlap. Otherwise GHC will compile the file-on-disk instead of grabbing the module from a package. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] cabal test-suite library recompilation
Hi all, I've recently started to move my tests to use the new cabal test-suite framework. Old setup: The cabal file compiles one library + a few executables. The library contains almost all of the code and exposes the necessary modules for use by the executables. The executables mainly consist of one main file. This way, the library is only compiled once and used multiple times by the executables. Great. One of the executables compile a test runner, and is handled similarly. New setup, using test-suite: I've deleted the executable section for the test runner and added a test-suite section instead. To my surprise, the library is compiled twice now. Hence, it takes twice as long. And it is a clear regression compared to my old setup. While waiting for a build to finish [ :) ], I just wanted to write an email and check if this is intentional or only an oversight. Or maybe a technical limitation for the time being? Thanks, Ozgur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: join (UHac <$> DHD)
You can still join us at the DHD >>= UHac, but the time is running out. http://www.haskell.org/haskellwiki/DHD_UHac Deadline: April 1 (no fooling!) We've also have a few updates: * We put the DHD program up, at least as much of it as we have. http://www.haskell.org/haskellwiki/DHD_UHac/DHD_Program * As you can see from the program, there is still room for more speakers. In particular, we'd like to hear from people coming outside Utrecht and the Netherlands. We'd also like to see more lightning talks. Send Sean an email with your idea: leat...@cs.uu.nl * UHac on Friday has moved to a "new" location. Actually, it's the same location as on Saturday and Sunday, so that should make things easier. See you in Utrecht! The Organizers: Sean Leather Jurriën Stutterheim Jurriaan Hage P.S. Make sure your Monad is also a Functor. P.P.S. Apologies for multiple copies. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] An idea to document inter department dependencies in Haskell
My dear Haskell folks, I work in a software company where I develop components that go into a really complex system that's built of several components developed by different teams that are geographically distributed. The components themselves run in a distributed manner across client and several servers. All our design documents are in wiki's (fashionably so). As a result of the above situation and the fact that our code base is not in Haskell, we are almost always dealing with "Oh I did not know this would effect that" and "Oh I have no clue what all this change will impact". I've been wondering if it would be a good idea to try and create a spec for the system in Haskell, such that would could get a better handle on the dependencies. Perhaps an EDSL, that would allow Product Managers to introduce new requirements - compilation failures would indicate the areas that would need to be touched. How is it different from having a spec in a diagram - well, in that case, we are requiring humans to look at the diagram to detect dependencies instead of the compiler telling me about the dependencies. I am about to start off with some implementation to capture my idea - I can articulate it better then. However, I just wanted to throw it out there to check if anyone's had some thought in this direction or if there is some prior art here. Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Inecxact map?
Am 13.03.2012 um 09:15 schrieb Morten Olsen Lysgaard: > I'm running a project where i want to generate a map of a rather large data > collection. The map is if the form: Data.Map.Map String a > I'd like to be able to do inexact lookups on the map. Firstly, ignore the > difference between upper lower case, that's easy. But secondly, have a > function: > > search :: (Num b) => Data.Map.Map String a -> String -> b -> [a] > > This function is like the normal lookup, but it takes an extra argument b. B > is the allowed character error rate. That is the Levenstein distance divided > on the length. It should return all the strings that has an error rate lower > that b and in a ordered manner, best first. > > Is it possible to design such a datastructure efficiently? > Does there already exist something like this? > If not, where would i begin to create this? You could take a trie and extend the lookup functions so that it also returns inexact matches up to a given error rate. That should be quite easy, because the definition of Levenshtein distance is recursive as well as the trie's lookup function. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Empty Input list
Kevin Clees writes: > Now my function looks like this: > > tmp:: [(Int, Int)] -> Int -> (Int, Int) > tmp [] y = (0,0) ^ > tmp xs y = xs !! (y-1) > If the function returns (0,0) it will blocked by another function. Personally, I think using "special" values like this is a code smell, and indicates poor design. There are many implicit assumptions, for instance that (0,0) isn't already a member of the input list, and that this is correctly handled by surrounding functions. Generally, it's much more desirable to encode this in the types, so I would vastly prefer the Maybe solution in almost all cases, which makes these assumptions explicit. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Inecxact map?
I'm running a project where i want to generate a map of a rather large data collection. The map is if the form: Data.Map.Map String a I'd like to be able to do inexact lookups on the map. Firstly, ignore the difference between upper lower case, that's easy. But secondly, have a function: search :: (Num b) => Data.Map.Map String a -> String -> b -> [a] This function is like the normal lookup, but it takes an extra argument b. B is the allowed character error rate. That is the Levenstein distance divided on the length. It should return all the strings that has an error rate lower that b and in a ordered manner, best first. Is it possible to design such a datastructure efficiently? Does there already exist something like this? If not, where would i begin to create this? Any advices or knowledge appreciated. -- Morten ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
