Hacker School, Thursday, June 12th, 2014

I spent essentially all of the official day working on a couple of Project Euler problems in Haskell. While I think this is an interesting way to learn Haskell, in retrospect it isn't very efficient, and it was frustrating at times. I expect it would have been faster and less frustrating if the problems I focused on came in the order of a Haskell learning curriculum. I may join the group who are working through Brent Yorgey's introduction to Haskell. Another promising resource is a book a fellow Hacker Schooler is writing, called Speeding Through Haskell. In the same vein, I had thought about trying these in Factor, but instead I think I would prefer to continue doing tutorials.

Also, I think not knowing basic things about how to go about the syntax inhibited my desire to pair on it. That might be wrong-headed, but I guess it would help me to do things that have the lowest barriers to pairing as I can find, at least until I get more at ease. Specifically, if we were both at that novice a level, I envision spending a lot of time saying, "Ok, let's split up to go look this up now."

We rounded off the week with presentations from various Hacker Schoolers, which lasted for about 5 minutes each. This brought me a wave of doubt, and I had to remind myself about not comparing myself to others. Beyond the doubt lay excitement, and it also spurred me on to make things! Tomorrow I will spend some time reprioritising based on the experiences this week.

After most people headed out, and the space quieted down, I started hunting for more Factor tutorial material, and found some good reads. I'm very excited about Factor.

Fridays are not obligatory here, and the optional job practice sessions don't start until next week. I will probably come tomorrow anyway. On the other hand, the library is holding a copy of Zellig Harris's A Theory of Language and Information: A Mathematical Approach for me to look at that beckons. They don't lend copies. There is no electronic version, and I can't afford a copy. I'll decide tomorrow.

I didn't ever get to my priority project, but I guess that's ok. It needs re-evaluating anyway. Also, it was nice to focus on something for a long period, rather than switching so much.

Here is my plan vs actual for the day, with notes:

Plan

  • Symlinks

    • Talk to Tahoe-LAFS devs about whether or not to proceed with this.

      Here is an idea for supporting symlinks on the Tahoe-LAFS side:

      When a symlink is encountered, instead of following it, first check to see if it exists in the LAFS. If not, follow it. It becomes the original. (There will be some weird logic for directories because of the depth firsting.) If it does exist, make a file, the contents of which are the capability to the existing copy. (Is there going to be a problem with read vs. write caps?)

  • Project Euler

    • look at the SICP description of tail recursion again to complete #2.
    • Attempt the first problem in Factor?
  • Factor

    • Proceed with the tutorial.
  • Maybe port some existing work to GitHub?

Actual

Project Euler

  • Finished #2 in Haskell, started #3 in Haskell

    The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143?

    As a first pass at this I wrote a Sieve of Eratosthenes, where I would iteratively pluck off the head of the list from 2 to n, and then recurse on the tail filtered to multiples of the head.

    sieve n = sieve_iterator [] [2..n]sieve_iterator p l =

    if l == [] then p else sieve_iterator (p ++ [head l]) [x | x <- l, not (mod x (head l) == 0)]

    This seemed to work fine, but was way too inefficient to get all the primes up to the square root of that large target number. (I later realised that I can't stop at the square root to get the largest prime factor and I'm wondering now if there is another insight to be had along that line of thinking...)

    So my next idea for a better approach was to actually factor the number as we go. I spent a long time working on a recursive function that looks a lot like the sieve, but at each iteration it returns the highest prime factor so far (the head of the last iteration if it was a factor), and the rest of the list that isn't a multiple of that prime truncated to the number passed in after factoring out the head of the list as many times as possible.

    I haven't yet gotten that function to work, though I did figure out a thing or two about Haskell variables along the way.

Factor

I read Beginning Factor – Shufflers & Combinators. These are my notes, but I recommend the article itself.

  • a quotation is just an anonymous function: [ "hello" print ]
  • a combinator is a word that takes a quotation as one of its inputs: 5 [ "hello" print ] times

"Factor uses quotations & combinators extensively for conditionals, sequence traversal, namespaces, closures, and more."

  • There is a "secret" auxiliary stack, called the retain stack, that acts basically as swap space, and that is used extensively by combinators under the hood.

  • Cleave Combinators are used when you want to apply multiple quotations to the same set of items on the top of the stack.

    • Instead of computing average as { 1 2 3 } dup sum swap length / ., use { 1 2 3 } [ sum ] [ length ] bi / .That's so much easier to read!
  • Spread Combinators are used when you want to apply a different quotation to different items on the top of the stack.

    E.g. bi* ( x y p q -- ) applies quotation p to x, then applies quotation q to y .

  • Apply Combinators are used when you want to apply a single quotation to multiple items on the top of the stack.

    E.g. instead of comparing strings like this: "john" "John" swap >upper swap >upper = ., use "john" "John" [ >upper ] bi@ = .

  • Some helpful sequence operators are filter, each, and all?.

  • iota ( n -- iota ) is like Python's range.

Wrote this post

.

Reflections

I can't believe an entire week is already over! It has been fantastic, as in like a fantasy. I'm so happy to be here.

Share