Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 25 September 2012 16:51, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. If you have listTest :: [a] - Bool, then head . dropWhile (not . listTest) . inits ? How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. -- 竹密岂妨流水过 山高哪阻野云飞 And for G+, please use magiclouds#gmail.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Call for discussion: OverloadedLists extension
Would that also work for vectors that have their length in their type? And while we are at it, how about overloaded tuples? Paul On Mon, Sep 24, 2012 at 7:19 PM, Simon Peyton-Jones simo...@microsoft.comwrote: | I remember a similar discussion a few years ago. The question of whether | or not overloading list literals a good idea notwithstanding, the problem | with this is that fromList for vectors is highly inefficient. So if | something like this gets implemented and if vector/array literals are one | of the main motivations then I really hope there will be no lists | involved. Would you like to remind us why it is so inefficient? Can't the vector construction be a fold over the list? Ah... you need to know the *length* of the list, don't you? So that you can allocate a suitably-sized vector. Which of course we do for literal lists. So what if fromList went fromList :: Int - [b] - a b where the Int is the length of the list? Simon ___ 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] Call for discussion: OverloadedLists extension
| Here at the University of Tübingen, I am co-supervising (together with | Jeroen Weijers) a student project implementing the OverloadedLists | extension for GHC. Achim Krause is the student who is working on the | project. We took into consideration earlier discussions on this topic | [1,2] before embarking on the project. | | Achim has worked on two approaches. Your second approach is this: | [x,y,z] | | as | | singleton x `mappend` singleton y `mappend` singleton z ; This approach is not good for long literal lists, because you get tons of executable code where the user thought he was just defining a data structure. And long literal lists are an important use-case. One other possibility is to use a variant of what GHC does for literal strings. Currently foo turns into unpackCString foo# where foo# is a statically allocate C string, and the unpackCString unpacks it lazily. Maybe we could make a literal [a,b.c] turn into unpack [a,b,c]# where [a,b,c]# is a statically-allocated vector? See http://hackage.haskell.org/trac/ghc/ticket/5218, which is stalled awaiting brain cycles from someone. I'm maxed out at the moment. I'd be very happy if you guys were able to make progress; I'm happy to advise. Open a ticket, start a wiki page, etc! Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
It also comes to my mind that you can use something similar to regular expressions and parsing, seeing your list as a word made of Int elements. I think you can achieve it using Parsec or attoparsec. One you define your basic combinators for 'odd', you can see your sublist as the minimal part of the list matching (even* odd)(even* odd)(even* odd)(even* odd) 2012/9/25 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com On 25 September 2012 16:51, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. If you have listTest :: [a] - Bool, then head . dropWhile (not . listTest) . inits ? How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. -- 竹密岂妨流水过 山高哪阻野云飞 And for G+, please use magiclouds#gmail.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ 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] Call for discussion: OverloadedLists extension
Simon Peyton-Jones wrote: | I remember a similar discussion a few years ago. The question of whether | or not overloading list literals a good idea notwithstanding, the problem | with this is that fromList for vectors is highly inefficient. So if | something like this gets implemented and if vector/array literals are one | of the main motivations then I really hope there will be no lists | involved. Would you like to remind us why it is so inefficient? Can't the vector construction be a fold over the list? Ah... you need to know the *length* of the list, don't you? So that you can allocate a suitably-sized vector. Which of course we do for literal lists. So what if fromList went fromList :: Int - [b] - a b where the Int is the length of the list? That's part of a problem. There are really two aspects to it. Firstly, a naive list-based implementation would be a loop. But when I write ([x,y] :: Vector Double) somewhere in an inner loop in my program, I *really* don't want a loop with two iterations at runtime - I want just an allocation and two writes. I suppose this could be solved by doing something like this: {-# INLINE fromList #-} fromList [] = V.empty fromList [x] = V.singleton x fromList [x,y] = ... -- and so on up to 8? 16? 32? fromList xs = fromList_loop xs But it's ugly and, more importantly, inlines a huge term for every literal. The other problem is with literals where all values are known at compile time. Suppose I have ([2.5,1.4] :: Vector Double) in an inner loop. Here, I don't want a complicated CAF for the constant vector which would have to be entered on every loop iteration. I'd much rather just have a pointer to the actual data somewhere in memory and use that. This is more or less what happens for strings at the moment, even though you have to use rewrite rules to get at the pointer which, in my opinion, is neither ideal nor really necessary. IMO, the right design shouldn't rely on rewrite rules. Also, strings give you an Addr# whereas vector supports ByteArray#, too. Since enumerated literals have been mentioned in a different post, I'll just mention that the Enum class as it is now can't support those efficiently for arrays because there is no way to determine either the length or the nth element of [x..y] in constant time. This would have to be fixed. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Call for discussion: OverloadedLists extension
| pointer to the actual data somewhere in memory and use that. This is | more or less what happens for strings at the moment, even though you | have to use rewrite rules to get at the pointer which, in my opinion, is | neither ideal nor really necessary. IMO, the right design shouldn't | rely on rewrite rules. Also, strings give you an Addr# whereas vector | supports ByteArray#, too. If it's not necessary, I wonder if you have an idea for the right design? I find it a lot easier to see what is wrong with the current situation than to think of solutions. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Call for discussion: OverloadedLists extension
Simon Peyton-Jones wrote: | pointer to the actual data somewhere in memory and use that. This is | more or less what happens for strings at the moment, even though you | have to use rewrite rules to get at the pointer which, in my opinion, is | neither ideal nor really necessary. IMO, the right design shouldn't | rely on rewrite rules. Also, strings give you an Addr# whereas vector | supports ByteArray#, too. If it's not necessary, I wonder if you have an idea for the right design? For strings, we could have something like this: data StringPtr stringFromStringPtr :: StringPtr - Int - String unsafeStringPtrToPtr :: StringPtr - Ptr CChar class IsString a where fromString :: String - a fromStringPtr :: StringPtr - Int - a fromStringPtr p n = fromString $ stringFromStringPtr p n abc would then desugar to fromStringPtr (address of abc) 3. Note that we couldn't just use Ptr CChar instead of StringPtr because stringFromPtr would only be safe if the data that the pointer references never changes. It's much trickier for general-purpose arrays. It's also much trickier to support both Ptr and ByteArray. I'd have to think about how to do that. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
Magicloud Magiclouds magicloud.magiclo...@gmail.com writes: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. Does f bound odds_so_far [] = [] f bound odds_so_far (x:xs) | odds_so_far == bound = [] | otherwise = x : f bound (odds_so_far + if odd x then 1 else 0) xs required_funciton = f 4 0 meet your criteria, or am I missing something? -- Jón Fairbairn jon.fairba...@cl.cam.ac.uk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fwd: [Haskell] ANNOUNCE: MFlow-0.1.5
Hi, This is an difficult problem in which the design principles of MFlow can help to creare a solution amazingly easily. I forward this message from, Web-devel because I think that it may be of interest A Web app. that creates Haskel computations from form responses. Store them, retrieve and execute them http://haskell-web.blogspot.com.es/2012/09/a.html Alberto 2012/9/18 Alberto G. Corona agocor...@gmail.com However if in a tab out of sync the user press refresh, the tab will refresh to the current state. I took care not to try to synchronize back as a consequence of a page that is in a forward state in one tab, as a consequence of navigating back in other tab. However I may have not considered all the edge extreme cases. There is a back detection primitive goingBack that allow the programmer to control the back behaviour in some special cases. For example if i want to step over a menu and present a default page, But if when the user go back i want to present the menu, I can detect this condition and present this menu, that did not appeared in a normal navigation: This code sets and get a default option in the menu, so the menu is not shown again in the navigation, except in the case that the user press the back button. Otherwise, the menu would be never accessible. However this is very specialized. normally the back button detection is not necessary. In a persistent flow even this default entry option would be completely automatic, since the process would restar at the last page visited. No setting is necessary. menu= do mop - getGoStraighTo back - goingBack case (mop,back) of (Just goop,False) - goop _ - do r - ask option1 | option2 case r of op1 - setGoStraighTo (Just goop1) goop1 op2 - setGoStraighTo (Just goop2) goop2 2012/9/18 Alberto G. Corona agocor...@gmail.com Hi Jake, right, it depends on the identification of the session: iAll the tabs share the same state because they share the same cookies. so if in one tab the use continue the interaction then the other tabs are out of sync. If the user goes to these other tabs and press any widget, the application will synchronize back to this page. This happens also if the user is logged in different computers. Alberto. 2012/9/18 Jake McArthur jake.mcart...@gmail.com Actually, I meant users that spawn multiple tabs from a single root session. You mentioned that you have some special support for the back button. What happens if I open a couple new tabs in which I may or may not go forward and backward. Do they all share the same state? Different states (how?)? Partially shared states? On Tue, Sep 18, 2012 at 12:33 PM, Alberto G. Corona agocor...@gmail.com wrote: Oh, I´m stupid. You mean web pages with multiple tabs I have not tested it. but each tab can be handled easily by a different server process.. or it can be handled in a single server process, like in a menu. For example, this code present different options, and the process renders different things depending on the response. The last option is a link to a different process, while the others( wlinks) are links that return back to the same process. The operator | is the applicative operator. a breakline is prepended to each link: data Ops= Ints | Strings | Actions | Ajax | Opt deriving(Typeable,Read, Show) mainf= do r - ask $ wlink Ints (bold increase an Int) | br ++ wlink Strings (bold increase a String) | br ++ wlink Actions (bold Example of a string widget with an action) | br ++ wlink Ajax (bold Simple AJAX example) | br ++ wlink Opt (bold select options) ++ (br +++ linkShop) -- this is an ordinary XHtml link case r of Ints- clickn 0 Strings - clicks 1 Actions - actions 1 Ajax- ajaxsample Opt - options mainf where linkShop= toHtml $ hotlink shop shopping . Alberto 2012/9/18 Alberto G. Corona agocor...@gmail.com: Hi Jake I don´t know what you mean with multiple tabs. The user management is simple, anonymous clients are identified with a cookie. if the user is logged (MFlow has widgets for logging-validation) the user is the identifier. The state of a process is associated to the client identifier and to the path invoked in the url requested. I don´t know if this answer your question Alberto 2012/9/18 Jake McArthur jake.mcart...@gmail.com: This sounds really cool. How do you handle users having multiple tabs? On Tue, Sep 18, 2012 at 11:26 AM, Alberto G. Corona agocor...@gmail.com wrote: Hi haskellers and specially the web developers. http://hackage.haskell.org/package/MFlow-0.1.5.3 MFlow is a is a Web
[Haskell-cafe] in the vector library, why define unbox tuples 2?
I'm looking at storing a data type with 7 fields in an unboxed vector, which means that I'll have to use GenUnboxTuple to create an instance for Unbox (a,b,c,d,e,f,g), but I was thinking that another solution is to use instance (Unbox a, Unbox b) = Unbox (a,b) recursively to create instance Unbox (a,(b,(c,(d,(e,(f,g)). Is there any reason I shouldn't say something like, import qualified Data.Vector.Unboxed as Vector data X = X Int Int Int Int Int Int Int toTuple (X a b c d e f g) = (a,(b,(c,(d,(e,(f,g)) toVector = Vector.fromList . map toTuple I guess I'm wondering if there is a technical reason why I should use an explicit Unbox instance for 7-tuples, or if it's just a convenience to have Unbox defined for tuples 2? Thanks, Jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Haskell] Well-Typed and Skills Matter offer Haskell courses in London in October
Hi Claude, I have a promo code which gives £50 off to make the Haskell Exchange £175. HASKELLX-2012-TE1. Note that this cost isn't profiteering - unfortunately running a conference (just getting a venue) is expensive. There will probably be some social aspect afterwards, I'll certainly go to a pub if anyone wants. I would love to see London HUG revived, I know people have tried (including in the very recent past, a few months ago), but as yet no one has managed to get any meetings going. Perhaps soon though. Hoodlums is a great event, more teaching and less talk based, but very well run and I highly recommend it! Thanks, Neil On Mon, Sep 24, 2012 at 9:11 PM, Claude Heiland-Allen cla...@mathr.co.uk wrote: Hi Andres, list, On 19/09/12 09:41, Andres Löh wrote: Oops, I hit send too prematurely, sorry for the seeming bluntness (but it is still a blunt message, can't apologize for that I suppose): No need to apologize. There's a need for informal meetings as much (or even more) as there is for courses and conferences. Thank you. Regarding London, I know there's the Haskell Hoodlums meetup (http://www.meetup.com/hoodlums/) Thanks, I wasn't aware of this one. I have signed up. Claude ___ 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] Call for discussion: OverloadedLists extension
Michael Snoyman wrote: Note that I wasn't necessarily advocating such a pragma. And a lot of my XML code actually *does* use two IsString instances at the same time, e.g.: Element (img :: Name) (singleton (href :: Name) (foo.png :: Text)) [NodeComment (No content inside an image :: Text)] In this particular case, would it make sense to use smart constructors instead? The idea is that you can put the polymorphism in two places: either make the output polymorphic, or make the input polymorphic. The latter would correspond to a type element :: (IsString name, IsString s, IsMap map) = name - map name s - [Element] element name map = Element (toName name) (toMap map) One benefit would be that the function will accept any list as a map, not just list literals. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Call for discussion: OverloadedLists extension
On Mon, Sep 24, 2012 at 5:53 AM, George Giorgidze giorgi...@gmail.comwrote: Our second approach to OverloadedLists is to avoid the construction of lists altogether. By typechecking and desugaring lists like [] ; [x,y,z] ; ['a' .. 'z'] ; as mempty ; singleton x `mappend` singleton y `mappend` singleton z ; genericEnumFromTo 'a' 'z' ; This is very interesting. As Michael mentions later, we already have mechanisms in place to work around the creation of constant strings for the Text and ByteString types, and they rely on a combination of GHC rewrite rules and knowledge about the internal representation of constant strings used by GHC. We are fortunate that GHC uses a very efficient representation to store constant strings, so doing the translation is efficient. Constant lists are another story entirely (for good reason); the generated object files are bloated and poorly laid out, when for simple types (integers and whatnot), I'd really like to see a packed array in the .data section. I would be interested to see if an approach that avoids list construction can also aim to achieve a more efficient object file layout, with the implied goal being to make fast translation to the runtime representation easily achievable. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
f x 0 = []f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] To: haskell-cafe@haskell.org From: jon.fairba...@cl.cam.ac.uk Date: Tue, 25 Sep 2012 10:16:52 +0100 Subject: Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type? Magicloud Magiclouds magicloud.magiclo...@gmail.com writes: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. How to do that? Combining lazy computing, I cannot figure out an efficient algorithm. Does f bound odds_so_far [] = [] f bound odds_so_far (x:xs) | odds_so_far == bound = [] | otherwise = x : f bound (odds_so_far + if odd x then 1 else 0) xs required_funciton = f 4 0 meet your criteria, or am I missing something? -- Jón Fairbairn jon.fairba...@cl.cam.ac.uk ___ 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] How to take a minimum sub list that only contain certain number of elements of certain type?
On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain rishab...@live.com wrote: f x 0 = [] f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] Tsk, tsk. So ugly. How's this: let f x = take x . filter odd f 4 [0..] ~ [1, 3, 5, 7] Notice that 0 is excluded, since 0 is *even*, not odd: http://en.wikipedia.org/wiki/Parity_of_zero If this is a serious problem, one can always just prepend zero: 0 : f 4 [1..] ~ [0, 1, 3, 5, 7] -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Call for discussion: OverloadedLists extension
So, in order not to have to rely on rewrite rules, would it be a good idea to add unpackCString to the IsString class? import GHC.Base (unpackCString#, Addr#) class IsString a where fromString :: String - a unpackCString :: Addr# - a unpackCString addr = fromString (unpackCString# addr) For lists something similar could probably be done. Sjoerd On Sep 25, 2012, at 10:01 AM, Simon Peyton-Jones simo...@microsoft.com wrote: | Here at the University of Tübingen, I am co-supervising (together with | Jeroen Weijers) a student project implementing the OverloadedLists | extension for GHC. Achim Krause is the student who is working on the | project. We took into consideration earlier discussions on this topic | [1,2] before embarking on the project. | | Achim has worked on two approaches. Your second approach is this: | [x,y,z] | | as | | singleton x `mappend` singleton y `mappend` singleton z ; This approach is not good for long literal lists, because you get tons of executable code where the user thought he was just defining a data structure. And long literal lists are an important use-case. One other possibility is to use a variant of what GHC does for literal strings. Currently foo turns into unpackCString foo# where foo# is a statically allocate C string, and the unpackCString unpacks it lazily. Maybe we could make a literal [a,b.c] turn into unpack [a,b,c]# where [a,b,c]# is a statically-allocated vector? See http://hackage.haskell.org/trac/ghc/ticket/5218, which is stalled awaiting brain cycles from someone. I'm maxed out at the moment. I'd be very happy if you guys were able to make progress; I'm happy to advise. Open a ticket, start a wiki page, etc! Simon ___ 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] [Haskell] ANN: HERMIT for GHC 7.6
[Note that original post was on the Haskell list, and not the Haskell-cafe list.] On Tue, 25 Sep 2012, Andrew Farmer afar...@ittc.ku.edu wrote: A new version of HERMIT (0.1.2.0) that is compatible with GHC 7.6 is now available on hackage. This release has essentially the same functionality as the 7.4-only pre-alpha release made before ICFP 2012. HERMIT (Haskell Equational Reasoning Model-to-Implementation Tunnel) is a plugin for GHC that provides an interactive interface for applying transformations directly to GHC's internal intermediate language, Core. This plugin is part of a larger HERMIT toolkit, which is being developed at the University of Kansas with the aims of supporting equational reasoning and allowing custom optimizations to be applied without modifying either GHC or the Haskell source code. Introduction to HERMIT via Neil Sculthorpe's Haskell Symposium 2012 talk: http://www.youtube.com/watch?v=x2QH3jJCJso Example transformations can be found in the examples folder, contained in the cabal source package. Hackage: http://hackage.haskell.org/package/hermit Github (for bug reports): https://github.com/ku-fpg/hermit Andrew Farmer Thank you and all the HERMIT Team for this! Does the HERMIT system provide an executable Haskell Core, that is, we can get an ordinary text file which can be executed by some version of GHC+HERMIT? oo--JS. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 26 September 2012 03:56, Gwern Branwen gwe...@gmail.com wrote: On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain rishab...@live.com wrote: f x 0 = [] f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] Tsk, tsk. So ugly. How's this: let f x = take x . filter odd f 4 [0..] ~ [1, 3, 5, 7] Notice that 0 is excluded, since 0 is *even*, not odd: http://en.wikipedia.org/wiki/Parity_of_zero If this is a serious problem, one can always just prepend zero: 0 : f 4 [1..] ~ [0, 1, 3, 5, 7] Except that your solution is incorrect, as Magicloud wanted the smallest _prefix_ that contained four odd numbers... -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
2012/9/25 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com On 25 September 2012 16:51, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, For example, I have an array [0..]. Now I want to take a sub list that starts from index 0, and only contain 4 odds, and is minimum result. The answer should be [0, 1, 2, 3, 4, 5, 6, 7]. What do you actually *mean*? When you say you have an array, but actually display a *list*, do you really mean you have something fitting into Data.Array, or do you really mean you have a list? When you say sub list do you mean a *slice* (a contiguous chunk) or a *subsequence* (elements preserve their order but there may be gaps). Or looking at your example, do you mean a *prefix* (n `take` xs for some n)? When you say odds I presume you mean odd integer, although the even/odd concept applies to Gaussian integers too (m+ni is even if it is divisible by 1+i, which turns out to be equivalent to m+ni being even (odd) iff m and n have the same (different) parity). When you say is minimum result, what does that mean? Does it mean the sum of the elements is minimal? (If you consider the list [1,3,5,7,-2,-4,-6,-8,-10,...] it is clear that a minimum result in that sense could be infinitely long.) Let's take just one interpretation: - the array is a list - whose elements are Integers - the result must be a prefix of the input - which contains four odd Integers - and is otherwise as short as possible. We'll generalise `take`: it will have an integer n, a predicate p, and a list xs. ptake :: Int - (a - Bool) - [a] - [a] ptake n p (x:xs) | n 0 = x : ptake (if p x then n-1 else n) p xs ptake _ _ _ = [] answer :: [Integer] - [Integer] answer xs = ptake 4 odd xs Now this is pretty trivial (it's _exactly_ `take` except for only counting elements where p is true), so that interpretation of the problem cannot be the right one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] 64-bit vs 32-bit haskell platform on Mac: misleading notice on Platform website?
Hi, I installed Haskell Platform 32-bit on a fresh 64-bit mac, because the page http://www.haskell.org/platform/mac.html says: Pick the 32-bit vesion, unless you have a specific reason to use the 64-bit version. The 32-bit one is slightly faster for most programs. Then, during the installation of a package, the following happeed: Loading package cairo-0.12.3.1 ... command line: can't load .so/.DLL for: /opt/local/lib/libz.dylib (dlopen(/opt/local/lib/libz.dylib, 9): no suitable image found. Did find: /opt/local/lib/libz.dylib: mach-o, but wrong architecture) That libz.dylib is a 64-bit library and it can't be used by 32-bit Haskell platform. QUESTION: It seems to me that most people, at least most who care about slightly faster programs, are likely to run into something like this - using native 64-bit libraries. Compatibility exists only in the opposite direction. Wouldn't it be appropriate to remove this notice and ask people to use the 64-bit version unless they have a specific reason not to? -- Eugene Kirpichov http://www.linkedin.com/in/eugenekirpichov We're hiring! http://tinyurl.com/mirantis-openstack-engineer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 26/09/2012, at 5:56 AM, Gwern Branwen wrote: On Tue, Sep 25, 2012 at 1:42 PM, Rishabh Jain rishab...@live.com wrote: f x 0 = [] f (x:xs) y | x `mod` 2 == 0 = x : (f xs y) | otherwise = x : (f xs (y-1)) f [0..] 4 [0,1,2,3,4,5,6,7] Tsk, tsk. So ugly. How's this: let f x = take x . filter odd Wrong. The original poster gave an explicit example in which even elements were *retained* in the output, they just weren't *counted*. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On Tue, Sep 25, 2012 at 8:17 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: Wrong. The original poster gave an explicit example in which even elements were *retained* in the output, they just weren't *counted*. You are at least the fourth person to email me now to point this out. I'm glad I could make four people's day better with the joy of correction... But I never said it was a full solution - please note that I did include the output of the function! One could consider it a partial solution, however: that gives you the _nth_ odd, so if you want a list of numbers up to the _nth_ odd, that gives you a stop condition - 'takeWhile =/ nth+1' etc. A 2N traverse (which laziness might fuse to just 1 traverse, dunno). -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On 26/09/2012, at 12:28 PM, Gwern Branwen wrote: On Tue, Sep 25, 2012 at 8:17 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: Wrong. The original poster gave an explicit example in which even elements were *retained* in the output, they just weren't *counted*. You are at least the fourth person to email me now to point this out. I'm glad I could make four people's day better with the joy of correction... But I never said it was a full solution - please note that I did include the output of the function! The tsk tsk is probably what made people so keen to reply. One could consider it a partial solution, however: that gives you the _nth_ odd, so if you want a list of numbers up to the _nth_ odd, that gives you a stop condition - 'takeWhile =/ nth+1' etc. That doesn't work either. Consider the list [1,1,1,1,1]. The element just after the 5th odd number in the list is 1; takeWhile (/= 1) will thus return [] instead of [1,1,1,1]. |A 2N traverse (which laziness might fuse to just 1 traverse, dunno). Not in this case, for fairly obvious reasons. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to take a minimum sub list that only contain certain number of elements of certain type?
On Tue, Sep 25, 2012 at 8:45 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: That doesn't work either. Consider the list [1,1,1,1,1]. The element just after the 5th odd number in the list is 1; takeWhile (/= 1) will thus return [] instead of [1,1,1,1]. I'm not sure that OP would prefer [1,1,1,1] to []. Another area of underspecification. -- gwern http://www.gwern.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church vs Boehm-Berarducci encoding of Lists
Wouldn't you say then that Church encoding is still the more appropriate reference given that Boehm-Berarducci's algorithm is rarely used? When I need to encode pattern matching it's goodbye Church and hello Scott. Aside from your projects, where else is the B-B procedure used? First of all, the Boehm-Berarducci encoding is inefficient only when doing an operation that is not easily representable as a fold. Quite many problems can be efficiently tackled by a fold. Second, I must stress the foundational advantage of the Boehm-Berarducci encoding: plain System F. Boehm-Berarducci encoding uses _no_ recursion: not at the term level, not at the type level. In contrast, the efficient for pattern-match encodings need general recursive types. With such types, a fix-point combinator becomes expressible, and the system, as a logic, becomes inconsistent. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church vs Boehm-Berarducci encoding of Lists
On Wed, Sep 26, 2012 at 12:41 AM, o...@okmij.org wrote: First of all, the Boehm-Berarducci encoding is inefficient only when doing an operation that is not easily representable as a fold. Quite many problems can be efficiently tackled by a fold. Indeed. Some operations are even more efficient than usually expected when operating on folds. For instance: snoc xs x f = xs f . f x People often recommend using ([a] - [a]) for efficiently building up lists without worrying about introducing O(n^2) costs through bad associativity, but the Boehm-Berarducci encoding gets you that and more (map g xs f = xs (f . g) ; map h (map g xs) = \f - xs (f . g . h)). -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 64-bit vs 32-bit haskell platform on Mac: misleading notice on Platform website?
Hi Eugene, To the best of my knowledge there is absolutely no reason to use the 32bit haskell on OS X (aside from memory usage optimization cases which likely do not matter to the *typical* user), and the community should probably update the recommendation to reflect this. I can certainly attest to having to baby sit new haskellers when installing and repeatedly say yes, do the 64 bit version, please, no, ignore the recommendation for 32bit, no one knows why its there, but its wrong what can we (the community ) do to address the fact that the haskell platform installer suggestions for os x are sadly completely backwards? (or am I completely wrong in my personal stance on this matter) cheers -Carter On Tue, Sep 25, 2012 at 7:52 PM, Eugene Kirpichov ekirpic...@gmail.comwrote: Hi, I installed Haskell Platform 32-bit on a fresh 64-bit mac, because the page http://www.haskell.org/platform/mac.html says: Pick the 32-bit vesion, unless you have a specific reason to use the 64-bit version. The 32-bit one is slightly faster for most programs. Then, during the installation of a package, the following happeed: Loading package cairo-0.12.3.1 ... command line: can't load .so/.DLL for: /opt/local/lib/libz.dylib (dlopen(/opt/local/lib/libz.dylib, 9): no suitable image found. Did find: /opt/local/lib/libz.dylib: mach-o, but wrong architecture) That libz.dylib is a 64-bit library and it can't be used by 32-bit Haskell platform. QUESTION: It seems to me that most people, at least most who care about slightly faster programs, are likely to run into something like this - using native 64-bit libraries. Compatibility exists only in the opposite direction. Wouldn't it be appropriate to remove this notice and ask people to use the 64-bit version unless they have a specific reason not to? -- Eugene Kirpichov http://www.linkedin.com/in/eugenekirpichov We're hiring! http://tinyurl.com/mirantis-openstack-engineer ___ 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