Overload the Prelude iterate to support list input

[shelbymoore3]

Had to overload the Prelude function iterate to support list input. The overload could be global (should be added to Prelude), no need to wrap in where. My example fibonacci sequence usage follows.

    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Make forward iteration explicit, and remove self referential space "leak" above due direct recursion on fibs.

    fibs = iterate (\x -> last x + last init x) [ 0 : 1 ] where
    	iterate :: ([a] -> [a]) -> [a] -> [a]
    	iterate f x =  iterate f (x : (f x))
    	-- iterate f x == [x, f x, f (f x), ...]

Or verbosely:

        fibs = iterate (\x -> fib -1 + fib -2 where fib i = | i==-1=last x | i==-2=last init x) [ 0 : 1 ]
        	-- negative indices in local function fib offset from end of list

P.S. Note I not using HUGS nor GHC, this is just in my head. The above are my unique solutions, didn't lift them from www. I am just learning FP and Haskell for first time in my head past few days. So this might be rubbish.

[shelbymoore3]

Prelude function iterate:

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3Aiterate

[shelbymoore3]

The suggested iterate function remains as stated. I just want to point out my example lamba function usage was not returning a list. Corrected:

fibs = iterate (\x -> [last x + last init x]) [ 0 : 1 ] where

Ditto (and I think I need to add the semicolon in the one line guard?):

fibs = iterate (\x -> [fib -1 + fib -2] where fib i = | i==-1=last x; | i==-2=last init x) [ 0 : 1 ]

[shelbymoore3]

Another correction, I need to use (++) append operation, not cons (:).

iterate :: ([a] -> [a]) -> [a] -> [a]
	iterate f x = iterate f (x ++ (f x))
	-- iterate f x == [x, f x, f (f x), ...]

[shelbymoore3]

Note scanl is more concise for fibs, but iterate is more general.

fibs3 = 0 : scanl (+) 1 fibs

[shelbymoore3]

fibs = 0 : scanl (+) 1 fibs

[igloo]

Thanks for the suggestion, but if you would like to propose changes to the libraries, please see:  http://www.haskell.org/haskellwiki/Library_submissions

However, a few things come to mind with your proposed change:

• If you did change the Prelude iterate rather than adding a new function, then you would probably break lots of code
• Your definition retains the whole list, so could cause space leaks
• last takes time linear in the length of its input, so performance where you want the last element (as current uses of iterate do) will not be good

[shelbymoore3]

Replying to igloo:

Thanks for the suggestion, but if you would like to propose changes to the libraries, please see:  http://www.haskell.org/haskellwiki/Library_submissions

Thanks for the pointer very much. That sure seems like overkill in terms of someone who just wants to spend a few minutes to contribute an idea. Are you sure you want to squelch the ideas-only submissions? I think successful mainstream paradigms encourage participation.

However, a few things come to mind with your proposed change: * If you did change the Prelude iterate rather than adding a new function, then you would probably break lots of code

How so? I have overloaded iterate on input and output type. Thus my proposed function shouldn't even be selected by the compiler for use with existing usage of iterate.

* Your definition retains the whole list, so could cause space leaks

That is the whole point. "space leak" means lazy evaluation cache, which is precisely what one wants sometimes, and when they don't want it, one should use another construct:

 http://www.coolpage.com/commentary/economic/shelby/Functional_Programming_Essence.html#Allocation_Size_Determinism

* last takes time linear in the length of its input, so performance where you want the last element (as current uses of iterate do) will not be good

But of course this change has nothing to do with current uses of iterate. It is a new function which iterates on entire lists in "free point" style of functional composition. That is the whole point.

Let's be careful to not jump too quickly to "won't fix" or "we don't accept ideas here". Sorry I am not yet knowledgeable about applying a patch to the source code of the libraries. I do not think that should be an impediment to submitting an idea. Why can't you have an area of this hackage of open suggestions for library enhancements, so that others can implement and apply the head patches at their leisure?

Thanks for making those points, so I could clarify.

[malcolm.wallace@…]

Replying to shelbymoore3:

Thanks for the suggestion, but if you would like to propose changes to the libraries, please see:  http://www.haskell.org/haskellwiki/Library_submissions

Thanks for the pointer very much. That sure seems like overkill in terms of someone who just wants to spend a few minutes to contribute an idea. Are you sure you want to squelch the ideas-only submissions? I think successful mainstream paradigms encourage participation.

It is exactly to encourage participation and consensus (rather than drive-by changes) that the Library submission guidelines exist. If you are not yet at a stage where you can create a patch yourself, then the best advice would be to post ideas on a mailing list like haskell-cafe@ or libraries@, in order to create discussion, gather support, and maybe persuade someone else to implement your idea as a patch. Posting ill-formed ideas to a bug-tracker (intended for a small number of core developers) is much less productive than using a dedicated discussion forum filled with many helpful users.

* If you did change the Prelude iterate rather than adding a new function, then you would probably break lots of code

How so? I have overloaded iterate on input and output type. Thus my proposed function shouldn't even be selected by the compiler for use with existing usage of iterate.

The Prelude 'iterate' is not currently overloaded, so making it overloaded may force type-inference changes in many usage positions, some of which may now become ambiguous and hence be rejected. Furthermore, your proposed overloading is not parametric in a way that can easily be captured by type classes. What is the least generalisation of the the two signatures for iterate?

    iterate :: (a   -> a)   ->  a  -> [a]
    iterate :: ([a] -> [a]) -> [a] -> [a]

Hint: there isn't one.

But of course this change has nothing to do with current uses of iterate. It is a new function which iterates on entire lists in "free point" style of functional composition. That is the whole point.

If it is a new function, unrelated to the existing one, then propose a new name for it, and you will likely find people more receptive to the suggestion.

Let's be careful to not jump too quickly to "won't fix" or "we don't accept ideas here".

"Won't fix" is not a moral judgement - it is just a bug-tracker tag. It usually means the ticket is incomplete, or posted to the wrong place, or that a reported bug is not a bug at all.

Why can't you have an area of this hackage of open suggestions for library enhancements, so that others can implement and apply the head patches at their leisure?

The bug-tracker is usually not the best place to post new ideas for feature requests, at least until they have been suggested and discussed in a open forum like a mailing list or IRC channel. Acceptance and refinement by the wider community is crucial.

[shelbymoore3]

Replying to malcolm.wallace@cs.york.ac.uk:

It is exactly to encourage participation and consensus (rather than drive-by changes) that the Library submission guidelines exist. If you are not yet at a stage where you can create a patch yourself, then the best advice would be to post ideas on a mailing list like haskell-cafe@ or libraries@,...

I didn't realize there was list specific to libraries. haskell-cafe@ would be much too noisy for such a small tweak change proposal as this.

...in order to create discussion, gather support, and maybe persuade someone else to implement your idea as a patch.

That is reasonable, except that small tweaks can be easily buried in a mailing list. I think a database format is preferable. I can't imagine the efficiency having my TODO list of ideas for some of the major projects I have worked on, being spread out in a mailing list. Also it is well known that consensus is not the way to write the best software. Small teams slaughter large monoliths.

Perhaps libraries@ is focused enough. I am not going to bother, I was just passing along to remind you guys that you forgot to generalize iterate for lists. Aren't lists a very important fundamental data structure in Haskell that is covered by just about every other library function?

But no big deal, I can write my own function. Why bother helping you by passing along the missing iterate for lists.

Posting ill-formed ideas to a bug-tracker (intended for a small number of core developers) is much less productive than using a dedicated discussion forum filled with many helpful users.

This idea is not ill-formed.

* If you did change the Prelude iterate rather than adding a new function, then you would probably break lots of code

How so? I have overloaded iterate on input and output type. Thus my proposed function shouldn't even be selected by the compiler for use with existing usage of iterate.

The Prelude 'iterate' is not currently overloaded, so making it overloaded may force type-inference changes in many usage positions, some of which may now become ambiguous and hence be rejected.

Perhaps that is because type inference doesn't scale and should be avoided entirely, except for local usage:

 http://lambda-the-ultimate.org/node/1277 (see slide #67)

Any one who relies on type inference globally can except such domino cascades generally.

Furthermore, your proposed overloading is not parametric in a way that can easily be captured by type classes. What is the least generalisation of the the two signatures for iterate? {{{ iterate :: (a -> a) -> a -> [a] iterate :: ([a] -> [a]) -> [a] -> [a] }}} Hint: there isn't one.

If I am not mistake, a type class can specify the signature that it expects.

If it is a new function, unrelated to the existing one, then propose a new name for it, and you will likely find people more receptive to the suggestion.

The name of a function implies its general semantics (function/purpose), and the type signature further narrows the semantics.

"Won't fix" is not a moral judgement - it is just a bug-tracker tag. It usually means the ticket is incomplete, or posted to the wrong place, or that a reported bug is not a bug at all.

Incomplete would be a more accurate tag than "won't fix". You do not know you won't end up fixing this when someone completes the library patch, or if you do, then your suggestion to me above was to waste my time.

The bug-tracker is usually not the best place to post new ideas for feature requests, at least until they have been suggested and discussed in a open forum like a mailing list or IRC channel. Acceptance and refinement by the wider community is crucial.

Yeah and it only took 20 years for Haskell to get here.

It is not totally unreasonable, except it doesn't scale. You are going to have adjust if Haskell is going to move out of the research and into mainstream, then busy business people are going to come and make quick inputs, and if you shut them out, then you are shooting yourself in the foot. We do not have time to go figure out all the little nuances of where you do you "consensus" communications on the side. Becoming a tenured member of the community should not be a requirement, because it does not scale.

You are really intelligient, but please do not forget the exponential function and the concept of scale.

Best regards. I did not modify the ticket status.

[shelbymoore3]

Replying to shelbymoore3:

Any one who relies on type inference globally can except such domino cascades generally.

Typo 'except' to 'expects'.

Furthermore, your proposed overloading is not parametric in a way that can easily be captured by type classes. What is the least generalisation of the the two signatures for iterate? {{{ iterate :: (a -> a) -> a -> [a] iterate :: ([a] -> [a]) -> [a] -> [a] }}} Hint: there isn't one.

If I am not mistake, a type class can specify the signature that it expects.

I do assume above that Haskell will not allow a type '[a]' where a type 'a' is expected. If type inference is allowing lists of types to be assumed where only a type was expected, then IMHO that was a mistake that opened a very big can of worms. Perhaps I am unaware of some usage that could not be accomplished otherwise, but it sure seems intuitive to me that conflation inference in that way would kill scale.

[malcolm.wallace@…]

Replying to shelbymoore3:

That is reasonable, except that small tweaks can be easily buried in a mailing list.

I agree that sometimes they get lost - but that can also be a sign of lack of support within the community. If a proposed change cannot gather an enthusiastic crowd who want it implemented, then the idea just isn't worth the effort of changing all the consequentially-impacted software etc to support it.

Also it is well known that consensus is not the way to write the best software. Small teams slaughter large monoliths.

The Haskell community values consensus, especially on standard and far-reaching components like the Prelude.

This idea is not ill-formed.

Has anyone pointed out yet that your 'iterate' function is non-terminating? Each recursive call builds a larger data structure (or rather, a thunk for it), but there is no base-case to the recursion, so no value is ever returned to the caller. This is the kind of beginner's mistake that is posted (and ironed out) every day on haskell-cafe@, or beginners@. The input of the community really can help you write better (working) code.

Perhaps that is because type inference doesn't scale and should be avoided entirely, except for local usage:

You will find it hard to convince anyone in the Haskell community that type inference is a bad idea. :-)

It is not totally unreasonable, except it doesn't scale. You are going to have adjust if Haskell is going to move out of the research and into mainstream, then busy business people are going to come and make quick inputs, and if you shut them out, then you are shooting yourself in the foot.

Letting any beginner who has studied Haskell for one week, modify the Prelude that is used by every Haskell programmer everywhere, without discussion and consensus, is what does not scale.

[shelbymoore3]

Replying to malcolm.wallace@cs.york.ac.uk:

Replying to shelbymoore3:

That is reasonable, except that small tweaks can be easily buried in a mailing list.

I agree that sometimes they get lost - but that can also be a sign of lack of support within the community. If a proposed change cannot gather an enthusiastic crowd who want it implemented, then the idea just isn't worth the effort of changing all the consequentially-impacted software etc to support it.

That is what I now call the Obama illogic. Here is a story about the wisdom (mass delusion) of crowds from 4000 years ago:

 http://goldwetrust.up-with.com/biblical-f3/god-s-governance-t129.htm#2313

Or perhaps you prefer the more scientific version:

 http://esr.ibiblio.org/?p=984

Also it is well known that consensus is not the way to write the best software. Small teams slaughter large monoliths.

The Haskell community values consensus, especially on standard and far-reaching components like the Prelude.

By you own (il)logic, you must cite a consensus on that before you autonomously attempt such a proclamation. ;) How dare you try to cut corners and be efficient (joke)! ...the socialist dog chases his tail...

I never proposed that my change be accepted without review of the community. I was only proposing that I be able to post my vote/suggestion efficiently (geez I really didn't want to diatribe you) and in an organized database. I take it that efficiency is too much to ask, unless you have tenure, then it is not.

I didn't run my software projects this way when I was the lead developer or a key one interfacing with QA. I do not understand what is gained by discouraging input, other than laziness to add an 'incomplete' tag. The size of the database costs you nearly nothing. If you are saying the time to read, consider and tag the input is too costly, I can argue you are never going to stop that (especially as something becomes more mainstream), unless you restrict access. In that case, you lose informational input also. There is no free lunch in the free market. Generally I think flattening the model is best (hierarchies do not scale well, they are brittle and rigid forming), and be clever about efficiency. Often a clever RegEx is enough to work wonders on productivity.

This idea is not ill-formed.

Has anyone pointed out yet that your 'iterate' function is non-terminating?

The standard Prelude function does not "terminate" either (is infinitely recursive):

http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-List.html#iterate

That is the whole point of the function! It is taking advantage of lazy evaluation caching, so the infinite list is only recursed as far as is needed by the usage the function. In my example use case, e.g. fibs !! index.

Each recursive call builds a larger data structure (or rather, a thunk for it), but there is no base-case to the recursion, so no value is ever returned to the caller. This is the kind of beginner's mistake that is posted (and ironed out) every day on haskell-cafe@, or beginners@. The input of the community really can help you write better (working) code.

So you are saying the standard Prelude was writting by beginners? ;)

Seems in one week I am somewhat ahead of your understanding, or am I somehow missing your point entirely?

Perhaps that is because type inference doesn't scale and should be avoided entirely, except for local usage:

You will find it hard to convince anyone in the Haskell community that type inference is a bad idea. :-)

If adding one overload to standard library function can break massive amounts of code, I do not need to convince anyone. The market will prove it. Socialists do not understand the power of the market. They have to re-learn the lessons of 4000 years ago, infinite times repeated (or maybe not, if you believe in an end time).

It is not totally unreasonable, except it doesn't scale. You are going to have adjust if Haskell is going to move out of the research and into mainstream, then busy business people are going to come and make quick inputs, and if you shut them out, then you are shooting yourself in the foot.

Letting any beginner who has studied Haskell for one week, modify the Prelude that is used by every Haskell programmer everywhere, without discussion and consensus, is what does not scale.

I did not modify the Prelude with this feature suggestion. I am only suggesting (not demanding) this suggestion be marked incomplete instead of "won't fix", and be entered into the database of things people can search for in future when looking for something to work on or explore.

And so far, looks like this beginner has made a reasonable strong case ;) Or at least not "ill formed".

[shelbymoore3]

Has anyone pointed out yet that your 'iterate' function is non-terminating?

Ah, I see your point now. I had a typo in my function, here is the obvious correction:

iterate f x = x ++ iterate f (x ++ (f x))

I thought you meant that it was infinitely recursive (which obviously standard Prelude is also), then I realized you meant that the function never returned a list. I wish you would have said that.

Actually I should modify the proposal and my usage to be more consistent with the current Prelude iterate and for maximum generality:

iterate f x = x ++ iterate f (f x)

Then my usage example changes to:

fibs = iterate (\x -> x ++ [last x + last init x]) [ 0 : 1 ] where 

Actually I think the way to solve the collision with standard Prelude is to make an overload of iterate that is even more general (but then this requires the dreaded type inference or a meaning also [a]), so thus I don't recommend this:

iterate :: (a -> a -> [a]) -> (a -> a) -> a -> [a]
iterate op f x = x 'op' iterate f (f x)

fibs = iterate (++) (\x -> x ++ [last x + last init x]) [ 0 : 1 ] where 

[shelbymoore3]

Actually none of that above works, we need instead an accumulator argument for the list, which solves the collision problem with standard Prelude iterate also:

iterate :: ([a] -> [a]) -> [a] -> [a] -> [a]
iterate f x y = y ++ iterate f (x ++ (f (x ++ y))) (f (x ++ y))

fibs = 0 : 1 : iterate (\x -> [last x + last init x]) [ 0 : 1 ] [] where 

IMHO, it is not most productive to mark useful input as "Won't fix", and have it disappear into a black-hole. It is more productive to mark as "Incomplete" and let people apply their effort later to make it complete, as has now been done. "Won't fix" should apply to something that should not be fixed (an entirely erroneous report with no chance of being ever fixed), not to something that is in a useful direction, but incomplete. "Won't fix" is effectually little different than a moral judgment, because it is a black hole. It is analogous to telling someone sorry you were misclassified on the "do not fly list" and are spending the rest of your vacation in a DHS holding area, but be comforted that it was not a moral mis-classification. Who cares. Give me back my vacation and my wasted time.

[shelbymoore3]

Better:

fibs = iterate (\x -> [last x + last init x]) [] [ 0 : 1 ] where 

[shelbymoore3]

Correction:

iterate f x y = y ++ iterate f (x ++ (f x)) (f x)

fibs = 0 : 1 : iterate (\x -> [last x + last init x]) [ 0 : 1 ] [] where

Alternative (IMHO the best):

iterate f x = x ++ iterate' f x [] where
   iterate' f x y = y ++ iterate' f (x ++ (f x)) (f x)

fibs = iterate (\x -> [last x + last init x]) [ 0 : 1 ] where

Alternative (less general):

iterate :: ([a] -> a) -> [a] -> a -> [a]
iterate f x y = y : iterate f (x ++ [(f x)]) (f x)

fibs = 0 : iterate (\x -> last x + last init x) [0] 1 where 

[simonmar]

Can we have an end to this please? Shelby, please take the discussion to the libraries list as Malcolm has already suggested. Clearly you're new to the community, please take the time to acquaint yourself with our working practices.