vegansk / nimfp

Nim functional programming library
MIT License
135 stars 9 forks source link

Add UnfoldRight and UnfoldLeft for Lists #10

Closed mratsim closed 7 years ago

mratsim commented 7 years ago

Hello vegansk.

Here is a PR for UnfoldRight and UnfoldLeft functions

I've also written two accompagnying tests: Splitting 12301230 into its digits in normal order (unfoldLeft) and reverse order (unfoldRight)

I've added the {. inline .} pragma as Haskell as a really long comment about it.

I don't have a benchmark to check performance on Nim though.

-- We treat unfoldr a little differently from some other forms for list fusion
-- for two reasons:
--
-- 1. We don't want to use a rule to rewrite a basic form to a fusible
-- form because this would inline before constant floating. As Simon Peyton-
-- Jones and others have pointed out, this could reduce sharing in some cases
-- where sharing is beneficial. Thus we simply INLINE it, which is, for
-- example, how enumFromTo::Int becomes eftInt. Unfortunately, we don't seem
-- to get enough of an inlining discount to get a version of eftInt based on
-- unfoldr to inline as readily as the usual one. We know that all the Maybe
-- nonsense will go away, but the compiler does not.
--
-- 2. The benefit of inlining unfoldr is likely to be huge in many common cases,
-- even apart from list fusion. In particular, inlining unfoldr often
-- allows GHC to erase all the Maybes. This appears to be critical if unfoldr
-- is to be used in high-performance code. A small increase in code size
-- in the relatively rare cases when this does not happen looks like a very
-- small price to pay.
--
-- Doing a back-and-forth dance doesn't seem to accomplish anything if the
-- final form has to be inlined in any case.
mratsim commented 7 years ago

I've update the code with your remarks. Regarding the test case, it's only checking compilation because the output of both functions would be complicated:

List((Field0: ?, Field1: false), (Field0: s, Field1: false), (Field0: s, Field1: false), (Field0: e, Field1: true), (Field0: c, Field1: false), (Field0: c, Field1: false), (Field0: u, Field1: true), (Field0: s, Field1: false), (Field0:  , Field1: false), (Field0: a, Field1: true), (Field0:  , Field1: false), (Field0: t, Field1: false), (Field0: i, Field1: true), (Field0:  , Field1: false), (Field0: s, Field1: false), (Field0: I, Field1: true))
List((Field0: I, Field1: true), (Field0: s, Field1: false), (Field0:  , Field1: false), (Field0: i, Field1: true), (Field0: t, Field1: false), (Field0:  , Field1: false), (Field0: a, Field1: true), (Field0:  , Field1: false), (Field0: s, Field1: false), (Field0: u, Field1: true), (Field0: c, Field1: false), (Field0: c, Field1: false), (Field0: e, Field1: true), (Field0: s, Field1: false), (Field0: s, Field1: false), (Field0: ?, Field1: false))
nigredo-tori commented 7 years ago

Thank you.