Posts tagged planet sipb

Why I Love Currying

Feb 12th

Posted by Patrick in Computers

8 comments

So I’ve been playing around with Haskell a lot lately and using it for various random stuff; I haven’t progressed to the point where it’s my go-to language for random programs (I still use Python for that), but I at least have an idea of how to use it. And there’s one feature of Haskell that I miss sorely when I write code in Python, or pretty much any other vaguely functional language: currying.

In Haskell, every function takes a single argument. A function of multiple arguments, such as map, which applies a function to every element in a list, actually only has one argument; for example, map can be interpreted either as taking a function and a list and returning a list, or as taking a function and returning a function that takes a list and returns a list. More formally, in Haskell, these two type declarations are equivalent:

map :: (a -> b) -> [a] -> [b]
map :: (a -> b) -> ([a] -> [b])

This process, of taking a multi-argument function and converting it into a series of single-argument functions is known as currying, after the mathematician Haskell Curry (who, obviously, is also the source of the name Haskell); the process of partially applying arguments to a function in this way is known as ‘partial application’, but is also called currying. One of the most obvious examples of currying is in sections: the function (0 ==) is syntactic sugar for (==) 0, and returns whether its argument is equal to zero. Furthermore, we can also partially apply the predicate to filter, to make a function that filters its argument on a fixed predicate. So, these three examples are completely equivalent:

removeZeros :: [Integer] -> [Integer]
removeZeros xs = filter (\x -> x /= 0) xs
removeZeros xs = filter (/= 0) xs
removeZeros = filter (/= 0)

(where /= is Haskell’s not-equal operator). The first is the most explicitly-written version, using no currying at all. The second curries the predicate; (/= 0) x is the same as x /= 0. Finally, since removeZeroes applied to an argument is the same as applying filter (/= 0) to it, we might as well define the former as the latter. Or, to take another example, look at the sortBy: it has type (a -> a -> Ordering) -> [a] -> [a], where Ordering is a datatype that can either be EQ, LT or GT for equal, less than, or greater than. So if you have some custom function you want to sort a list on, you can just say mySort = sortBy f and it will be the same as writing mySort xs = sortBy f xs, only cleaner and neater. Or in my Data.Nimber module (specifically lines 38, 39, and 43), many operations on Nimbers that’re required in order for me to call then ‘numbers’ are just the identity operation. So instead of saying abs x = x, I can just say abs = id.

Furthermore, without currying, you couldn’t have variadic functions; in order to work inside Haskell’s type system, the two types a -> b -> c and a -> (b -> c) have to be the same type. The full explanation involves typeclasses, and is (in my opinion) worth a read, because it’s a good explanation of a pretty horriblexcellent (it’s both at once, you see) type system hack.

As an aside, this also means that id :: a -> a, the identity function, is in a sense the same thing as ($) :: (a -> b) -> a -> b, which is function application. You can see this by substituting (b -> c) for a in the type of id, then removing parentheses:

id :: a -> a
id :: (b -> c) -> (b -> c)
id :: (b -> c) -> b -> c

So, in particular, f `id` x is the same as f $ x, which is just f x. Another way to think of this is that f `id` x = id f x = (id f) x = f x.

,

Variadic Functions in Haskell

Jan 12th

Posted by Patrick in Computers

5 comments

Most modern languages have some kind of printf analogue: a function that takes a format string, and a series of things to be inserted into that string, and formats them all accordingly. At first glance, Haskell’s strong type system would seem to preclude this. There’s no built-in system for writing functions that take variable numbers of arguments, and it seems like it would be difficult to write one. The standard approach is to take a list instead, but this fundamentally doesn’t work for printf, since you’re going to be wanting to print Integers, Strings, and Floats. It’s possible to just pre-apply show to everything, but that’s not really a good idea, because you might want to show them in a different way than the built-in show does. You can use an extension called existential types to create a list of PrintfWrappers which wrap integers/floats/strings (more on that below), but that requires your users to manually do the wrapping, which is, once again, not a good idea. Haskell’s Text.Printf module takes a third approach. Look at the following lines:

instance (IsChar c) => PrintfType [c]
instance PrintfType (IO a)
instance (PrintfArg a, PrintfType r) => PrintfType (a -> r)

instance PrintfArg Integer
instance (IsChar c) => PrintfArg [c]

printf :: (PrintfType r) => String -> r

Here’s how to interpret this: PrintfType is the type of things that can be printed to. Printing to a String just gives you a string, much like sprintf in C or Perl, printing to an IO () will actually print it out (so you can use it like a normal printf in do blocks, a behavior which I personally find distasteful.). However, printf will return undefined when asked to return an IO r; the reason that you can nevertheless return one is that only declaring IO () as an instance of PrintfType is invalid according to Haskell 98.

PrintfArg, by comparison, are the elements that are valid arguments to printf; they basically consist of the various WordN/IntN types, Integer, Float, Char, and (IsChar c) => [c]. The point of the last instance is that, while you can’t have a specific version of a polymorphic type be an instance of a typeclass, you can restrict it to types whose parameters are themselves instance of another typeclass; the only instance of isChar is Char.
So now that we have that clarified, let’s suppose we want to call printf with “%s %d %f” “foo” 42 3.1, passing it the format string, String, an Integer, and a Float. This causes printf’s type to become

printf :: String -> String -> Integer -> Float -> String

Does this match the pattern (PrintfType r) => String -> r? Let’s go in reverse. String is an instance of PrintfType, and Float is an instance of PrintfArg, so Float -> String is an instance of PrintfType. Therefore, Integer -> (Float -> String) is an instance of PrintfArg, and so is String -> (Integer -> (Float -> String)). Dropping parentheses, this becomes String -> Integer -> Float -> String. So the types all check out. If you pass an invalid type, then you’ll run into something that isn’t an instance of PrintfArg and so the types won’t check.

I mentioned above that if you use something called ‘existential types’, you can do something similar. The way it works is that you define a new type whose data constructor only requires that its argument be of a given typeclass. Look at the following example

{-# LANGUAGE ExistentialQuantifiers #-}
data Box = forall s. (Show s) => Box s

boxes = [Box 2, Box "f", Box [8,3]]\

showBoxes :: [Box] -> String
showBoxes [] = ""
showBoxes ((Box x):xs) = show x ++ " " ++ showBoxes xs

When you run showBoxes boxes, you get 2 "f" 83, exactly as you’d expect. Note that, however, the function unbox (Box x) = x cannot be written; it would have to be of type (Show s) => Box -> s, and there’s just no real way to do that. So once you’ve wrapped something up in a Box, you can only get at it by showing it. From this, you can see how to pass a heterogeneous list to printf. The reason that this approach is suboptimal is that it would require Text.Printf to export a Printf data constructor which would wrap up everything to make it of the appropriate type, and that would be rather annoying, especially since it relies on show preserving enough information for you to format the number after reading it back in.

This pattern can obviously extended to any other variadic, heterogeneous function, as long as you can define a suitable typeclass that its arguments must all be instances of. And that’s not really a restriction at all; if you can’t specify a behavior that the instances must have, then you don’t really know what you can do with the arguments, and so you can’t do anything at all!

,

Electrons are not like planets

Jan 1st

Posted by Patrick in Physics

No comments

One of my first posts on this blog was about the stability of the atomic nucleus; given that it consists of a bunch of positive/neutral charges clumped together, why doesn’t it fly apart? The answer involves the strong force, which is strong at atomic distances but miniscule at inter-nuclear distances; on distances comparable to that of an atomic nucleus, it’s strong enough to overcome the electromagnetic repulsion. But there’s another question, and it involves the model of orbiting electrons.

Classically (meaning without quantum mechanics), the electron is pictured as a pointlike particle orbiting the nucleus. For simplicitly, we’ll look at the hydrogen atom. The electron orbits at the Bohr radius , a_0=5.3 \times 10^{-13} cm, which can’t really be derived in an easy way from theory; we’ll just take it as a given. So the acceleration the electron undergoes is q^2 / m_e r^2 (using cgs units to avoid factors of 1/4\pi \epsilon_0 and such everywhere), using good old F=ma.

However, there is a problem: any accelerating charge radiates energy. The reason for this is, roughly speaking, an accelerating charge has more energy in its electromagnetic field, so you therefore have to expend more energy to accelerate it; since an atom is a closed system, there can be no energy source, so it ‘extracts’ it by spiraling inwards. The derivation of formula is complicated, but it turns out that a particle of charge q accelerating at a rate a will radiate energy at a rate

P=\frac{2 q^2 a^2}{3 c^3}=\frac{2q^6}{3m_e^2r^4c^3}

(the second equation what we get when we plug in our value for acceleration).

So what’s the energy of an electron orbiting its atom? The kinetic energy is equal to \frac{1}{2}mv^2=\frac{1}{2}rF=q^2/2r, and the potential energy is equal to $-q^2/r$, so the total energy is just

E=-q^2/2r

Considering both energy and radiated power as functions of time, we get dE/dt=-P; but since the only variable that can change is the radius, we then get the following differential equation for the radius:
r'=-\frac{4q^4}{3m^2c^3r^2}

The method of solving this equation isn’t important; I used Mathematica. What is important is the solution:
r=\left(a_0^3-\frac{4q^4t}{c^3m^2}\right)^{1/3}

where a_0 is the Bohr radius I mentioned earlier. This will obviously become finite at t_0=\frac{a_0^3m_e^2c^3}{4q^4}; plugging in the cgs values for these constants, we get that t_0=3.11 \times 10^{-11} seconds

So what’s the answer? One is to use the Bohr model, which requires a minimum energy; the electron cannot fall farther into an energy well. This model works to a certain extent, but fails with more complicated atoms; not only that, but it predicts that the hydrogen atom has a minimum nonzero angular momentum, which is not the case. But a full treatment of the failings of the Bohr model goes beyond what I know.

,