In the previous post I discussed an algorithm for calculating the square root of a number. This short post will show an implementation in Haskell. I did one implementation using the State Monad but to be quite honest it was an impenetrable mess! I’m sure part of that was down to my embryonic Haskell skills but perhaps the State Monad was a bad fit for this problem? The implementation below uses a fold over a list of digit pairs and the start state for the fold is based on ‘the largest integer squared’ with subsequent calculations using ‘doubling’ – as Read More

## Author: BanditPig

## Stateful Folding.

This is not a monad tutorial. These are my notes and code to help me grok monads. ðŸ™‚ As part of learning Haskell there is for some, perhaps many – including me, the ascent of Mount Monad! I’m finding the way to ‘get it’ is to keep chipping away at Monads, read, absorb, write some code then rinse and repeat! This creates a familiarity with the symbols, with the do, >>= and >> being different faces of the same coin. As part of this launderette of code I started writing simple Haskell functions and then pulled them apart and rewrote Read More

## The expressiveness of Haskell – Substrings.

Earlier today I was talking with a colleague about extracting a substring of a string given the start and end indices. He showed me an implementation in Javascript and I wrote one in Java and then looked at the Java 8 implementation which I’ve pasted below.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
public String substring(int beginIndex, int endIndex) { if (beginIndex < 0) { throw new StringIndexOutOfBoundsException(beginIndex); } if (endIndex > value.length) { throw new StringIndexOutOfBoundsException(endIndex); } int subLen = endIndex - beginIndex; if (subLen < 0) { throw new StringIndexOutOfBoundsException(subLen); } return ((beginIndex == 0) && (endIndex == value.length)) ? this: new String(value, beginIndex, subLen); } |

If we reformatted this we’d have 6 lines of code. Now for some Haskell… What is it we do when extracting a substring? For me, I think of it as taking the string, dropping the chars up to the start index and then from that getting chars up to the end index and Read More

## The Root of the Problem. Part 1.

I suppose since the advent of cheap calculators the task of working out the square root of a number has become simply a matter of pressing a few buttons and reading off the answer. But there was a time when we didn’t have calculators or slide rules or log tables – like these! Before all of these we used one of several ways to calculate a square root. One technique, which I’ll describe, is a bit like long division and works like this… First off group the numbers in pairs starting from the least significant digit before any decimal point Read More

## Ever Decreasing Circles.

A few days ago I came across this really interesting problem on the ‘dailyprogrammer‘. Here’s the question. Imagine you’ve got a square in 2D space, with axis values between 0 and 1, like this diagram. The challenge today is conceptually simple: can you place a circle within the square such that exactly half of the points in the square lie within the circle and half lie outside the circle, like here? You’re going to write a program which does this – but you also need to find the smallest circle which solves the challenge, ie. has the minimum area of Read More

## Dual Numbers and Differentiation. Part 3.

Previously we looked at using Dual numbers get the value of the first derivative of a function. As useful as this is there is more potential if we can also obtain the second derivative. My initial, naive, approach to this was to extend the idea of a Dual to that of a Triple like this. data Triple a = T a a a deriving (Show). Creating Triple somehow seemed ‘wrong’, or if not wrong then certainly clumsy as can be seen in some of the code below.

1 2 3 4 5 6 |
data Triple a = T a a a deriving (Show) instance Fractional a => Fractional (Triple a ) where fromRational n = T (fromRational n) 0 0 (T g g' g'') / (T h h' h'') = T (g / h) ((g * h' - h * g')/ h * h) secDiff where secDiff = ( 2*h'*(g*h' - h*g') - h*(g*h'' - h*g'')) / (h * h * h) |

Note how messy the code is! It’s the result of apply the quotient rule to the result of applying the quotient Read More

## Kaprekar’s Constant.

Just recently I came across ‘Kaprekar’s Constant‘ and maybe Mr Kaprekar had too much spare time… but still, it is quite interesting. The idea is to take a 4 digit number where the digits are not all the same then make the largest and smallest numbers possible with these digits, subtract the smaller from the larger then rinse and repeat with the result of the subtraction. e.g start with 4123 and in fact all 4 digits ‘converge’ to 6174! Now this is too good an opportunity for some Haskell… First let’s take an integer and extract its digits Read More

## Dual Numbers and Differentiation. Part 2.

At the end of the previous post I had intended this posting to be an exploration of a recursive definition of Dual that will give an infinite (lazy) list of derivatives. However, there’s still a lot to play with using our simple data Dual a = Dual a a Let’s try a simple function of two variables… and at we have Now we can evaluate at using dual numbers with a subscript of x or y to ‘remember’ where it came from…i.e we want but really are the ‘same thing’. Notice that the coefficients of are the same as the Read More

## Dual Numbers and Differentiation. Part 1.

Overview Just recently I came across the interesting and, at first viewing, the rather abstract idea of dual numbers. I suppose they are no more or less abstract than other numbers… anyway the idea is similar to that of complex numbers where we have Dual numbers are quite similar, we have the dual number d as So now lets take this idea of a dual number and explore how adding, multiplying and dividing them might be defined. Addition and subtraction are simple – we just add the corresponding components – in much the same way that Read More

## Haskell, Vectors and Simple Mechanics – part 4.

I think this post will wrap up the series on Vectors and Simple Mechanics and we’ll look at Simple Harmonic Motion (SHM) and compare the numerical solutions to SHM using the naive step function from the previous post – aka the ‘Euler‘ step and the more accurate ‘Euler-Cromer‘ method. Here’s the Euler Step from last time.

1 2 3 4 5 |
step :: Accnf -> Float -> State -> State step f dt st@(t, r, v) = (t', r', v') where t' = t + dt r' = r ^+^ v ^* dt v' = v ^+^ f st ^* dt |

a very simple change to the above yields the ‘Euler-Cromer‘ step where the ‘new velocity‘ rather than the ‘old‘ is used to determine the ‘new‘ position.

1 2 3 4 5 |
ecStep :: Accnf -> Float -> State -> State ecStep f dt st@(t, r, v) = (t', r', v') where t' = t + dt r' = r ^+^ v' ^* dt v' = v ^+^ f st ^* dt |

These two functions have the same signature, Accnf -> Float -> State -> State which allows us to generalise a solution based Read More