Conversation started Feb 12, 2013 at 9:02.
Xeo
Xeo
Feb 12, 2013 09:02
@R.MartinhoFernandes What's scan? :)
@Xeo scan f xs = map f $ zip xs $ drop 1 xs, I think.
Xeo
Xeo
@R.MartinhoFernandes My mind isn't yet ready to comprehend that, still booting.
@Xeo In C# xs.Zip(xs.Skip(1), f).
Xeo
Xeo
@R.MartinhoFernandes IOW, adjacent_for_each?
@Xeo Yeah, I guess. I don't think you will find it in Boost though. Did I mention Boost.Range sucks?
Xeo
Xeo
Feb 12, 2013 09:11
@R.MartinhoFernandes std::mismatch :D
@R.MartinhoFernandes fine, throw your fancy words at me :P
@Xeo That needs to be thoroughly abused to work as a generic scan.
But yes, it is a specialization of scan.
Xeo
Xeo
@R.MartinhoFernandes Just return always true.
user142019
My health is bad and I feel bad.
@Xeo And now what? You need to output something somewhere.
Xeo
Xeo
Feb 12, 2013 09:14
Hm
Then, transform!
So you need to hide what would be the ouput iterator in the predicate.
@Xeo Right, with next(). That's essentially the same implementation I gave in Haskell above.
Xeo
Xeo
:D
Oh um, I'm not familiar with std::mismatch. Is there a canonical example?
Xeo
Xeo
@LucDanton scan through two sequences, return where the first mismatch is. Common substring might be an example.
@R.MartinhoFernandes And I in C++!
What's a mismatch? I mean I understand the meaning, but what's a mismatched pair?
Feb 12, 2013 09:16
@LucDanton !=, or custom predicate.
Xeo
Xeo
@LucDanton == or predicate returns false.
Xeo
Xeo
@R.MartinhoFernandes Btw, I think that invokes UB actually, since it would dereference the end iterator.
@LucDanton "fooqux" and "foobar" mismatch at the fourth element.
user142019
Feb 12, 2013 09:16
It seems awfully convenient but I'm not sure I've ever needed it.
user142019
I can't find the tweet on Twitter. :(
@Xeo Just passing it to next is enough.
user142019
> Whatever. You did a shitty job anyways.
user142019
lol
Xeo
Xeo
@R.MartinhoFernandes Huh?
Feb 12, 2013 09:17
@Xeo next increments it, so you hit UB before you get to dereference anything.
Xeo
Xeo
@R.MartinhoFernandes Ah
@Zoidberg funny that
That's another reason to have scan be a thing, instead of hacking it up with the existing blocks.
Xeo
Xeo
So you'd need transform(next(first), last, first, f)
user142019
@thecoshman I agree.
Xeo
Xeo
Feb 12, 2013 09:18
(aka swap the iters)
Also, it's damn useful.
@Xeo Same thing (also, you forgot the out argument)
next(first) is UB for empty ranges.
@R.MartinhoFernandes I tried to express mismatch in terms of find_if and zip and I have to agree here.
Xeo
Xeo
@R.MartinhoFernandes Hm... true
user142019
Oh cool GHC gets a new I/O manager which works better in parallel programs.
Is zip from Boost.Range, or are we assuming some custom implementation?
Feb 12, 2013 09:21
Mine.
Ah, so Boost.Range doesn't even have zip.
Really, what non-trivial algorithm does Boost.Range have?
I treat it as a library of building blocks. Much like I think of Boost.Iterators: boost::iterator_facade and boost::iterator_adaptor.
@LucDanton Except is sorely misses non-trivial building blocks like scans and bind/whateveryouwanttocallit :(
So to answer: I don't trust Boost.Range to provide anything!
Bind is particularly important because you can build almost everything on it.
Feb 12, 2013 09:23
@R.MartinhoFernandes To clarify: building blocks for writing generic ranges, lol. Not for using ranges.
Does it have folds (aka cata)?
@R.MartinhoFernandes What kind of bind are we talking about here?
@LucDanton The monadic one.
Gimme bind, ana, and cata and I can do everything!
@R.MartinhoFernandes No.
So nothing at all.
None of those three.
Feb 12, 2013 09:25
It provides range versions of the Standard algorithms which is only useful for consuming ranges. The only thing you have to compose new ranges are the adaptors, which are really, really limited.
Wait, maybe ana.
There's a generator thing, right?
Xeo
Xeo
@R.MartinhoFernandes Wtf is with those names.
@LucDanton Yeah, I tried those.
The largest negative integer is -1. — A. Jesse Jiryu Davis Apr 30 '12 at 19:48
@Xeo Three somewhat abstract algorithms, so they have arbitrary names.
Feb 12, 2013 09:26
Oh, another way of stating my opinion: Boost.Range is a framework for writing new range adaptors :p
@R.MartinhoFernandes Tranforming a function into a range?
oh man, I got my opes up then when I noticed it said my rep was at 2k
it was only rounding it up :(
I feel cheated
@Xeo Bind is somewhat like a generic flatten. Cata is also known as fold. Ana is a generic generator.
What are unfold & friends?
Doesn't have that.
You can make_range over the Boost.Iterator thingies that does that -- it may not be generators in the spirit, but I think practically that's what you'd want to use.
Xeo
Xeo
Feb 12, 2013 09:29
@R.MartinhoFernandes ...
Let me check the signature of unfold.
Yeah, it's nowhere near as powerful :/ On top of being nasty to write.
@Xeo They are the most minimalistic subset you need to implement almost every range algorithm you can think of.
Xeo
Xeo
@R.MartinhoFernandes "generic flatten" kinda sounds like fold, y'know. Or what do you mean with "flatten"?
Boost.Range does not need to provide such a minimalistic core (that would be silly), but there is no way to implement that core on top of Boost.Range, which is my point: it only has trivial crap.
@Xeo >>= from Haskell? SelectMany from C#. flatMap from Scala.
Yeah, boost::make_function_input_iterator() can only deal with infinite 'ranges' or ranges that terminate in a finite number of steps known at construction time, lol.
Feb 12, 2013 09:31
Just note that you should not start this memory device from a free ball situation... — sehe 14 secs ago
@R.MartinhoFernandes Btw, isn't that unfair? It's one particular kind of bind, but not the most general, is it?
Xeo
Xeo
@R.MartinhoFernandes Ah, that kind of flatten - flattening nested ranges.
@LucDanton Together with cata and ana, it is general enough for a fairly extensive definition of "everything".
am I the only one to have noticed that the majority of new accounts asking very basic C++ things with very strange limits on what can be used tend to have a distinctly oriental sounding name?
@R.MartinhoFernandes Are you saying, because Boost Range is not, in fact, a functional programming library, but rather a range library, it is mostly useless?
@thecoshman yup. It means, only Indian colleges still teach C++
Feb 12, 2013 09:34
@LucDanton And as I said, I wouldn't expect it to have those three as functions right there. But I would want to be able to implement them on top of the existing ones (that would prove whatever core it provides is generic enough).
Xeo
Xeo
@R.MartinhoFernandes Okay, now on to ana... how does that work? :3
@R.MartinhoFernandes Okay. I've never read about the three together. I knew about the cata/ana duality, and I knew about the power of bind/join and in particular in the context of range-like thingies. But separate!
@sehe No, I'm saying it only provides trivial algorithms. Even the slightly complex ones are unattainable.
Well I mean I consider flattening as one kind of joining. Which I've known to be important here.
I think I'm repeating myself here.
Feb 12, 2013 09:36
@LucDanton Well, you can pick different equivalent subsets that are as powerful. This is just the smallest one I know.
@Xeo Do you know unfold from Haskell?
user1357851
@sehe and yet this (C++) is the most populated room?
@R.MartinhoFernandes soooo. We need Boost Linq after all (<ducks/>)
> You don’t understand computational complexity. This is probably the most annoying comment any theoretician can make. The purpose of the big-O notation is to codify succinctly the experience of any good programmer so that we can quickly teach it. If you are discussing a problem with an experienced programmer, don’t assume he can’t understand his problems. here
Better, counting_range is trivially built on top of ana. It is one particular specialization of it.
@Telkitty Think about the common title "die hard". What does it mean :)
user142019
@R.MartinhoFernandes TIL: unfold and it seems cool.
Xeo
Xeo
Feb 12, 2013 09:38
@R.MartinhoFernandes Negative.
@LucDanton Gladly, but I’ve no idea what you mean by that. :p
Ana comes from Greek "up", because it builds up your structure (in our case, a range) from the ground (in the case of counting_range from one or two integers).
@R.MartinhoFernandes Okay I think I've got it. I've read about ana+cata+a third, where the third is flattening/joining/projecting depending on terminology (e.g. DB stuff for the last). I've connected the dots on my own between bind and this kind of joining, but only insofar as I'd call, say, (>>=) :: [a] -> (a -> [b]) -> [b] a kind of range-joining. And you're saying I can think of (>>=) in its entirety as being that third operation?
Cata comes from Greek "down", because it breaks down your structure (the range) into a simple result, like the sum.
@R.MartinhoFernandes Properly spelt: Kata (κατά)
user142019
Feb 12, 2013 09:39
Katakana.
@sehe If you are curious, LINQ does have this core.
Kat in't bakkie
@KonradRudolph Scroll up!
Xeo
Xeo
@R.MartinhoFernandes Ah, I see.
user142019
@sehe ( ͡° ͜ʖ ͡°)
Feb 12, 2013 09:41
@Zoidberg The famous Paul Klee Emoticon
user142019
Lenny.
Xeo
Xeo
Suddenly, with the names explained, cata and ana make sense. :P
@LucDanton Ah, that. So what do you want to hear?
@LucDanton Does join x = bind x id help? (i.e. bind does not have less power than join)
user142019
How could that work? id :: a -> a but >>= :: m a -> (a -> m b) -> m b.
Xeo
Xeo
Feb 12, 2013 09:43
Question: What associativity does >>= in Haskell have?
@KonradRudolph Are there instances where you know or suspect that Requires failed to produce an error (and e.g. instance you had some template instantiated which produced its usual annoying error way too deep)? Where it produced an error too soon?
@Zoidberg join :: m (m a) -> m a
@R.MartinhoFernandes No. It's one of the first thing you taught me about monads (or perhaps the Cat?), and which I did find very helpful though. The problem is the copula in 'bind is the third operation' tbh :p
user142019
@R.MartinhoFernandes Ohh. :P
Up to now I was convinced that 'some instances of bind are the third operation'. You're telling me that's the wrong kind though.
Feb 12, 2013 09:47
Oh, no, I'm not saying that. The triplets (ana, cata, join) and (ana, cata, bind) have the equal expressive power (I don't remember how to prove that, though).
So (ana, cata, join) would be equally acceptable.
user142019
@Xeo left.
Yeah, but here is that the full bind or is it constrained?
user142019
infixl 1 >>=
@LucDanton I haven’t actually used the clause in a real code base yet, just in toy examples so I cannot speak from experience. I don’t see how it could fail to produce an error, but it may lead to cryptic error messages
@LucDanton The full one.
You can build it from (ana, cata, join) (which is the part of the proof I don't remember)
Feb 12, 2013 09:48
@R.MartinhoFernandes I shall contemplate this new knowledge.
 
Conversation ended Feb 12, 2013 at 9:48.