best way to code this Classic List Threaded 10 messages Open this post in threaded view
|

best way to code this

 Hi, A simple example of something I was trying to do but it had some questions along the lines of "the best way to do this". Given a list   l = [a] and an a-list   alist = [ (a,b) ] the idea is to find all the items in l which are in alist and then create a list [b] so the overall function should be  [a] -> [ (a,b) ] -> [b] the solution is straightforward:  l1 = filter (\x -> isJust (lookup x alist)) l  l2 = map (\x -> fromJust (lookup x alist)) l1 `fromJust` used in the construction of l2 won't fail, because only the elements for which the lookup succeeded are in l1. This would be something called `filterMap` but I couldn't find such a function in the list library, but it seems like there just has to be one defined in a library somewhere. the above seems clumsy, i'm wondering how to make it "more pretty". generally i was also wondering if the above construction is as inefficient as it looks because of the double-lookup, or would the compiler actually be able to optimize that code into something more efficient ?  this code is not being used on large sets of data so efficiency doesn't matter, I'm just curious. Thanks, Brian _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this

 I think you're looking for `mapMaybe` :-) - LyndonOn Sun, May 31, 2015 at 11:30 AM, wrote:Hi, A simple example of something I was trying to do but it had some questions along the lines of "the best way to do this". Given a list   l = [a] and an a-list   alist = [ (a,b) ] the idea is to find all the items in l which are in alist and then create a list [b] so the overall function should be  [a] -> [ (a,b) ] -> [b] the solution is straightforward:  l1 = filter (\x -> isJust (lookup x alist)) l  l2 = map (\x -> fromJust (lookup x alist)) l1 `fromJust` used in the construction of l2 won't fail, because only the elements for which the lookup succeeded are in l1. This would be something called `filterMap` but I couldn't find such a function in the list library, but it seems like there just has to be one defined in a library somewhere. the above seems clumsy, i'm wondering how to make it "more pretty". generally i was also wondering if the above construction is as inefficient as it looks because of the double-lookup, or would the compiler actually be able to optimize that code into something more efficient ?  this code is not being used on large sets of data so efficiency doesn't matter, I'm just curious. Thanks, Brian _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this

 On Sun, 31 May 2015 11:47:01 +1000 Lyndon Maydwell <[hidden email]> wrote: > I think you're looking for `mapMaybe` :-) > > yes. yes i am. lol. i even had the Maybe module open and just didn't get all the way to the end. although after looking at my problem, i realized i need to save those elements of the list that weren't matched. that makes it slightly more complicated.  but i did find partition which works nicely. thanks! Brian _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this

 In reply to this post by Lyndon Maydwell f as alist = [ b | (a, b) <- alist, a `elem` as ] perhaps? On Sat, 30 May 2015 6:47 pm Lyndon Maydwell <[hidden email]> wrote:I think you're looking for `mapMaybe` :-) - LyndonOn Sun, May 31, 2015 at 11:30 AM, wrote:Hi, A simple example of something I was trying to do but it had some questions along the lines of "the best way to do this". Given a list   l = [a] and an a-list   alist = [ (a,b) ] the idea is to find all the items in l which are in alist and then create a list [b] so the overall function should be  [a] -> [ (a,b) ] -> [b] the solution is straightforward:  l1 = filter (\x -> isJust (lookup x alist)) l  l2 = map (\x -> fromJust (lookup x alist)) l1 `fromJust` used in the construction of l2 won't fail, because only the elements for which the lookup succeeded are in l1. This would be something called `filterMap` but I couldn't find such a function in the list library, but it seems like there just has to be one defined in a library somewhere. the above seems clumsy, i'm wondering how to make it "more pretty". generally i was also wondering if the above construction is as inefficient as it looks because of the double-lookup, or would the compiler actually be able to optimize that code into something more efficient ?  this code is not being used on large sets of data so efficiency doesn't matter, I'm just curious. Thanks, Brian _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this

 Note that all proposed solutions are in O(n²) while this can be realized in O(n log n) (sort both list then match them in order). It depends on your use case if this is worthwhile.-- JedaïLe dim. 31 mai 2015 à 07:17, Alex Hammel <[hidden email]> a écrit :f as alist = [ b | (a, b) <- alist, a `elem` as ] perhaps? On Sat, 30 May 2015 6:47 pm Lyndon Maydwell <[hidden email]> wrote:I think you're looking for `mapMaybe` :-) - LyndonOn Sun, May 31, 2015 at 11:30 AM, wrote:Hi, A simple example of something I was trying to do but it had some questions along the lines of "the best way to do this". Given a list   l = [a] and an a-list   alist = [ (a,b) ] the idea is to find all the items in l which are in alist and then create a list [b] so the overall function should be  [a] -> [ (a,b) ] -> [b] the solution is straightforward:  l1 = filter (\x -> isJust (lookup x alist)) l  l2 = map (\x -> fromJust (lookup x alist)) l1 `fromJust` used in the construction of l2 won't fail, because only the elements for which the lookup succeeded are in l1. This would be something called `filterMap` but I couldn't find such a function in the list library, but it seems like there just has to be one defined in a library somewhere. the above seems clumsy, i'm wondering how to make it "more pretty". generally i was also wondering if the above construction is as inefficient as it looks because of the double-lookup, or would the compiler actually be able to optimize that code into something more efficient ?  this code is not being used on large sets of data so efficiency doesn't matter, I'm just curious. Thanks, Brian _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this~~

 In reply to this post by Alex Hammel On Sun, 31 May 2015 05:17:10 +0000 Alex Hammel <[hidden email]> wrote: > f as alist = [ b | (a, b) <- alist, a `elem` as ] > > perhaps? perhaps.  i have no idea how that works.  but don't spoil it for me though, i'm going to go of and study it :-) @Chaddai . this is for very small lists, so optimization in the form of sorting and binary lookup is definitely not worth the effort. Here's what I finally wrote.  partitionMaybe is a modified version of partition from the List library. unsure what the ~(ts, fs) syntax is though, removing the `~` doesn't seem to matter. this seems fairly clean. i noticed that partition simply uses foldr.  it looks like select is just a helper so that partition isn't cluttered.  i'm unsure why select was broken out as a separate function instead of just being in a where clause.  possibly to be able to assign it a an explicit type signature ?  more likely it has something to do with the fact that in the library partition is declared inline. extract :: [(String,b)] -> [String] -> ([b], [String]) extract alist l =   let inList s = lookup (uppercase s) alist       (l1, l2) = partitionMaybe inList l   in    (l1, l2) partitionMaybe :: (a -> Maybe b) -> [a] -> ([b],[a]) partitionMaybe p xs = foldr (select p) ([],[]) xs select :: (a -> Maybe b) -> a -> ([b], [a]) -> ([b], [a]) select p x ~(ts,fs) | isJust y = ((fromJust y):ts,fs)                     | otherwise = (ts, x:fs)   where     y = p x _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this~~

 > f as alist = [ b | (a, b) <- alist, a `elem` as ] > > perhaps? perhaps.  i have no idea how that works.  but don't spoil it for me though, i'm going to go of and study it :-)It's a list comprehension. I hope that's not too much of a spoiler :)  unsure what the ~(ts, fs) syntax is though, removing the `~` doesn't seem to matter.  this seems fairly clean. i noticed that partition simply uses foldr.  it looks like select is just a helper so that partition isn't cluttered.  i'm unsure why select was broken out as a separate function instead of just being in a where clause.  possibly to be able to assign it a an explicit type signature ?You can assign type signatures in `let` and `where` clauses: f = let i :: Int i = 1 in increment i where increment :: Int -> Int increment = (+) 1This is often quite a good idea. Type signatures are excellent, machine-checkable documentation.  extract :: [(String,b)] -> [String] -> ([b], [String]) extract alist l =   let inList s = lookup (uppercase s) alist       (l1, l2) = partitionMaybe inList l   in    (l1, l2) partitionMaybe :: (a -> Maybe b) -> [a] -> ([b],[a]) partitionMaybe p xs = foldr (select p) ([],[]) xs select :: (a -> Maybe b) -> a -> ([b], [a]) -> ([b], [a]) select p x ~(ts,fs) | isJust y = ((fromJust y):ts,fs)                     | otherwise = (ts, x:fs)   where     y = p x Couple of things: `fromJust` is a code smell. In general, you should at least consider replacing it with `fromMaybe (error msg)` where `msg` is a more useful error message than '*** Exception: Maybe.fromJust: Nothing'. Of course in this particular case, that will never come up because you can prove that `y` is never Nothing using the guard condition. But in that case, it's better practice to use pattern matching and let the compiler prove it for you:select p y ~(xs,ys) = acc \$ p y where acc (Just x) = (x:xs, ys) acc Nothing = ( xs, y:ys)The `partitionMaybe` function looks a bit odd to me. The computation you're trying to express is 'If this computation succedes, return whatever value it returned, but if it fails return some default value'. This is not a natural use of the Maybe data type: that's what Either is for. There's even a `partitionEithers` library function. `lookup` returns Maybe, not Either, but we can fix that. Here's my go (I've changed around the API a little bit as well) toEither :: a -> (Maybe b) -> Either a b toEither _ (Just x) = Right x toEither y Nothing = Left y lookupEither :: Eq a => a -> [(a,b)] -> Either a b lookupEither key assocs = toEither key \$ lookup key assocs uppercase :: String -> String uppercase = map toUpper extract :: [String] -> [(String,b)] -> ([String],[b]) extract xs assocs = let xs' = map uppercase xs eithers = map (\x -> lookupEither x assocs) xs' -- spoilers: same as [ lookupEither x assocs | x <- xs' ] in partitionEithers eithers main :: IO () main = print \$ extract ["Foo", "Bar"] [("FOO",1), ("BAZ",2)]This differs slightly from your algorithm in that it returns '(["BAR"],), where yours would return (["Bar"],). If preserving the original case in the output, I would either write a `caseInsensitiveLookup` function, or use a case insensitive text data type. _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

Re: best way to code this~~

 On Mon, 01 Jun 2015 16:10:47 +0000 Alex Hammel <[hidden email]> wrote: Thank you so much for all the info !  Really appreciate it. > extract :: [String] -> [(String,b)] -> ([String],[b]) > extract xs assocs = >     let xs' = map uppercase xs >         eithers = map (\x -> lookupEither x assocs) xs' >         -- spoilers: same as [ lookupEither x assocs | x <- xs' ] >     in partitionEithers eithers > > This differs slightly from your algorithm in that it returns > '(["BAR"],), where yours would return (["Bar"],). If preserving > the original case in the output, I would either write a ok. big surprise, i like your version much better. however, i'm unclear why you didn't just use   eithers = map (\x -> lookupEither (uppercase x) assocs) xs instead of mapping everything to uppercase first. meanwhile i need to get with the list comprehension program.  i use python list comprehensions all the time, and yet i continue to use map in haskell. how weird is that ? Brian _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners