“The Neophyte’s Guide to Scala” by Daniel Westheide

This Scala tutorial, called "The Neophyte’s Guide to Scala" can be considered as an auxiliary resource of #progfun. It is particularly good at getting started with Scala, and to delve a bit deeper with it.

From November 2012 to April 2013, I created and published a blog series called , targeted at aspiring Scala enthusiasts who have already made their first steps with the language and are looking for more detailed explanations.

Enjoy!

Advertisement

Comprehensions

Patterns in Functional Programming

Prompted by some recent work I’ve been doing on reasoning about monadic computations, I’ve been looking back at the work from the 1990s by Phil Trinder, Limsoon Wong, Leonidas Fegaras, Torsten Grust, and others, on monad comprehensions as a framework for database queries.

The idea goes back to the adjunction between extension and intension in set theory—you can define a set by its extension, that is by listing its elements:

$latex \displaystyle \{ 1, 9, 25, 49, 81 \} &fg=000000$

or by its intension, that is by characterizing those elements:

$latex \displaystyle \{ n^2 \mid 0 < n < 10 \land n \equiv 1 (\mathop{mod} 2) \} &fg=000000$

Expressions in the latter form are called set comprehensions. They inspired a programming notation in the SETL language from NYU, and have become widely known through list comprehensions in languages like Haskell. The structure needed of sets or…

View original post 3,366 more words

Why work doesn’t happen at work –Jason Fried

Following is an interesting TED talk by Jason Fried of 37signal on why it is difficult to get any work done at work.

He argues that M&Ms (managers and meetings) are the real problem at work. How can we change that? I am certain that Jason is not suggesting to fire and cancel all M&Ms. Instead he has the following three suggestions to get more work done at office:

1 No talk Thursday. Enforce 4 hour of uninterrupted and quite time once a week.

2 Promote passive way of communication via chat and email application.

3 Just cancel the next meeting, if you have the power.

Check this podcast out to see whether you can relate it with your work environment, and improve it by promoting these suggestions. Thanks.

UVa 10706. Number Sequence with F#

This post describes an algorithm to solve UVa 10706: Number Sequence problem from UVa OJ. Before outlining the algorithm, we first give an overview of this problem in the next section.

Interpretation

This is a straight-forward problem, which however, requires careful introspection. Our objective is to write a program that compute the value of a sequence , which is comprised of the number groups . Each consists of positive integers written one after another and thus, the first digits of are —

11212312341234512345612345671234567812345678912345678910123456789101112345678910

It is imperative to note that, the value of has the following range . Realize that, the maximum value of is indeed Int32.MaxValue. In the provided test cases, the values of are stated. We simply have to compute ; therefore, we are required to write a function that has following signature: .  That is —

f: 10 --> S.[10] = 4
f: 8  --> S.[8]  = 2
f: 3  --> S.[3]  = 2

Note also that the maximum number of test cases is 25. Question for the reader: What is the maximum possible value of for the specified sequence , which is constituted of  ?

We hope that by this time, it is clear where we are headed towards. In next section, we outline an algorithm to solve this problem. But, before moving further, we would like to recommend you to try to solve it yourselves first and then, read the rest of the post. By the way, we believe that the solution that we have presented next can be further optimized (or, even a better solution can be derived). We highly welcome your feedback regarding this.

Algorithm

Recall that, is constituted of number groups . In order to identify the digit located at the position of , we first determine the number group   that digit is associated with and then, we figure out the    digit from .

To do so, we first compute the length of each number group . Consider the number group till

112123123412345123456…12345678910

As mentioned, this sequence is basically constituted of  as shown below (with their respective lengths).

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 3
1 2 3 4              --> 4
1 2 3 4 5            --> 5
1 2 3 4 5 6          --> 6
1 2 3 4 5 6 7        --> 7
1 2 3 4 5 6 7 8      --> 8
1 2 3 4 5 6 7 8 9    --> 9
1 2 3 4 5 6 7 8 9 10 --> 11

It implies that the length of can be computed from the length of as shown below.

eqn-1

Using Eq.1, we calculate the cumulative sum of each number group as follows.

eqn-2

Why do we calculate cumulative sum? The purpose in this is to be able to simply run a binary search to determine which number group the digit belongs to in time. For example, consider i=40.

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 6 
1 2 3 4              --> 10
1 2 3 4 5            --> 15
1 2 3 4 5 6          --> 21
1 2 3 4 5 6 7        --> 28
1 2 3 4 5 6 7 8      --> 36 
1 2 3 4 5 6 7 8 9    --> 45
1 2 3 4 5 6 7 8 9 10 --> 56

Using binary search, we can find out that contains the digit. Then, using a linear search, we can simply derive the first four digits of to eventually find out the corresponding digit, 4.

eqn-3

Similarly, for i=55, we can figure out that the digit is indeed 1.

Implementation

Next, we outline a F# implementation of the stated algorithm. We start with computing the cumulative sums of the lengths as follows. Continue reading “UVa 10706. Number Sequence with F#”

Howard Mansell on F# Type Providers and the R Programming Language

In the following podcast, Howard Mansell talks about F# type provider and R programming language, which can be summarized as:

“F# 3.0 introduces an exciting and innovative new programming language feature – Type Providers. This functionality allows types that are dynamically generated during development to be used in statically typed code, bringing many of the benefits of dynamic languages to statically typed languages, without sacrificing the safety of static typing.

At BlueMountain, Howard has built and open-sourced a type provider that allows the functionality of the open-source R statistical package to be used from F# in a very fluid manner. This brings the broadest suite of statistical functionality available on any platform to F#. Howard introduces type providers and their (hitherto unexplored) uses for cross-language meta-programming. He also discusses some of the difficulties of bridging the strong static typing of F# with the loose dynamic typing of R” [1].

References

1 http://vimeo.com/49045879