5 kyu

Lambda Calculus: Lists as folds I

27 of 95JohanWiltink
Description
Loading description...
Algorithms
View
AllIssues1Questions2Suggestions3Show Resolved
  • Please sign in or sign up to leave a comment.
  • once_upon_a_potato Avatar

    This comment has been hidden.

  • UlrichBerntien Avatar

    I need a hint to optimze the Python code. I can't reach the 12s time limit.

    My current times are:

    • cons - Completed in 0.03ms
    • snoc - Completed in 0.24ms
    • map - Completed in 0.03ms
    • filter - Completed in 0.25ms
    • Random number test - failed with time out after 677 passed test cases.

    snoc and filter is slower because this functions use recursion.

    Is there a general method to optimize the functions with recursion?

  • Kacarott Avatar

    Python translation, complete with syntax checker.

    Once approved and happy with the syntax checker, I will use it in some other katas.

  • Blind4Basics Avatar
     
    expected your code to be in Lambda Calculus form
offending line: "const empty  = xs => isEmpty(xs)===True"

    ..... meh... :/ whyyyy...?

    • Blind4Basics Avatar

      mmmh... I beleive I got the "why"...

      (did I already tell you how much I suck at LC? x) )

    • JohanWiltink Avatar

      Show me where === is in Lambda Calculus and you will have shown me something I didn't know. :P

      That's not how isEmpty works. It returns a Church Boolean, which chooses between its two arguments.

      What you are doing could work in JS, because it has a notion of object equality; but in LC, what you are doing can never work, because it is undecidable if one function is "the same as" another function.

      Does this answer your question?

    • Blind4Basics Avatar

      yup x)

      (did I tell...? Err... Yeah I did. x) )

      note: I believe I didn't get that failing tests when running the samplet tests. Could you check?

    • JohanWiltink Avatar

      I checked, and if I add the offending line the example tests already fail me. ( They run in Preloaded in JS, so you get whacked on the head before you Attempt. Seemed nicer - people might do things that solve the kata but are not LC. )

    • JohanWiltink Avatar
      Question marked resolved by JohanWiltink 4 years ago
  • Blind4Basics Avatar

    Is it me or you didn't specify that map and filter always use cons and never snoc? (but it's entierly possible I just (yet again) didn't understand anything to the task... You know how much I... like this stuff... XD )

    • JohanWiltink Avatar

      map and filter return lists, so use the c that is passed to them ( later - you might not even have realised there will be a c and an n coming later ). See the definition of a list, in the code blocks up top.

      But if you can write them in terms of cons or snoc, be my guest. I don't think it can be done, because a list has to be parametrised over c and n, so you can't hardcode them. But if you can .. you'll have shown me something I didn't know. :P

      It might be possible to hardcode the c and n I use for testing. I'll add a test that uses different ones, so your solution has to use what's coming in.

    • JohanWiltink Avatar

      The JS random tests will now test if a list is correctly encoded as c => n => c(x)(c(y)(c(z)(n))). It will pass varying appropriate values for c and n.

    • JohanWiltink Avatar

      You can write them in terms of cons ( and nil ). Of course you can, because those are already parametrised over c and n.

      The input list is encoded as a foldr, which associates to the right, so snoc is not very useful, but it can be done.

      Realistically, stick to cons. Once you have cons, you can use that ( and nil, which you have Preloaded, and foldr, which is just an input list ) to do anything. Only cons itself has to be written primitively.

    • JohanWiltink Avatar

      This fork, which you can't see yet I guess, shows map and filter by way of foldl and snoc instead of foldr and cons.

      But it can't be done in the kata, because you need a polymorphically existentially quantified List type for that, and the kata doesn't have that. ( The sequel will. Hi carrott! )

      Also, it defines foldl and snoc in terms of foldr, cons and nil to arrive at a monstrosity that seems to run quadratically, with nested folds, over the list while building ( which is then probably optimised to a single linear foldr by GHC in post. GHC is quite aggressive at that ).

      In short, don't do it. In this kata, you can't even do it. Do it the way Dog intended.

    • JohanWiltink Avatar

      I guess you could do it in JS. The above pertains to Haskell.

    • Blind4Basics Avatar

      (I cannot see the fork as long I didn't solve the kata, btw ;) )

    • JohanWiltink Avatar

      Yeah, I know that. There are two solutions to that, and I think you know them. :P

      It is indeed possible to do map and filter in terms of snoc in JS; see here. You need foldl in terms of foldr for that, which can be done but may be unintuitive.

      Can I do anything to help you enjoy Lambda Calculus, or at least get better at it?

  • Kacarott Avatar

    While filter is still undefined, there is one sample test:

    toList (ListsAsFolds.filter (bool false true . even) (cons 1 nil)) `shouldBe` []

    Which throws type complaints, making it hard to solve the kata step by step (especially if you define filter last, like I did).

    If it isn't possible to make it calm down, then I would suggest removing that test.

    • JohanWiltink Avatar

      Apologies. I missed that. Fixed now.

      You can now solve it step by step. It's calmed down. Better. :] Thanks.

      Suggestion marked resolved by JohanWiltink 4 years ago
    • Kacarott Avatar

      Looks good. Very nice kata, it kind of left me wanting to do more with fold lists.

    • JohanWiltink Avatar

      Thanks. Should I be doing a sequel?

      I could probably figure out a way to deal with numbers, and have you do get, set, length, init, last, includes, indexOf, find, some, every, and yes, foldl ( which also gives reverse ). Also, zip might be fun.

    • Kacarott Avatar

      I would certainly enjoy it! Would numbers just be Church/some other encoding, or something specific to folding?

    • JohanWiltink Avatar

      Church numerals are very Lambda Calculus, but I am leaning towards just embracing native unsigned integers, with predefined zero, succ and pred functions.

      Call it optimized Peano. That would minimise the changes to the parser as well ( no operator scribbles ).

      "Something specific to folding" - do you have something in mind? I can't imagine what, but I would love to know if such a thing could exist.

    • JohanWiltink Avatar

      You could of course convert the Peano nums to Church or Scott yourself. Church has its advantages.

      I would probably also do everything fully typed ( in Haskell ). Takes a bit of wrapping and unwrapping, but that's compile time overhead only and does fit with the theme.

  • monadius Avatar

    JavaScript: I suggest to add const to the initial solution:

    const cons = undefined

const snoc = undefined

const map = undefined

const filter = undefined

    The initial solution is wrapped inside a funciton. It is not a good practice to define variables inside a function without const, let, or var. Moreover, it is prohibited in strict mode.

    • JohanWiltink Avatar

      I know it's not good practice, but it's legal. And normally, I absolutely don't do this unless it's a code golf. My ( only ) reason to do it here is that this is embedded Lambda Calculus in JavaScript, and I wanted it to look more like plain LC ( all the parens are bad enough ). Technically, it doesn't really matter ( and I could quite easily fix the parser to require, and not even just allow, it ).

      Do I really have to? Will it improve your opinion of the kata if it's added?

    • monadius Avatar

      It is legal now. But when proper modules are implemented it will be necessary to add var, let, or const to all variables which are exported. So I think it is better to add const to all declarations now.

    • JohanWiltink Avatar

      I'll get on it.

    • JohanWiltink Avatar

      I've added consts to the initial solution, made it mandatory, and updated the description.

      Suggestion marked resolved by JohanWiltink 4 years ago
  • monadius Avatar

    Haskell: The initial solution does not compile:

    test/ListsAsFoldsSpec.hs:3:32: error:
    Module ‘ListsAsFolds’ does not export ‘map’
  |
3 | import ListsAsFolds (cons,snoc,map,filter)
  |                                ^^^

test/ListsAsFoldsSpec.hs:3:36: error:
    Module ‘ListsAsFolds’ does not export ‘filter’
  |
3 | import ListsAsFolds (cons,snoc,map,filter)
  |                                    ^^^^^^