Accidentally in Code

Author: Cate

I ♥ Haskell
I knew there was a tighter way to write the derangement code for my assignment, but my Haskell was really rusty and what I had was fast, so I gave up. This morning it came to me – now I have 5 lines instead of 8. I do not have any idea how one would express this in pseudo code, though and it’s probably really quite difficult to read if you’re not familiar with Haskell.
```
derange1 :: Int -> [[Int]]
derange1 x = perm 0 (makeList x)

makeList :: Int -> [Int]
makeList 0 = []
makeList n = makeList (n-1) ++ [n]

perm :: Int -> [Int] -> [[Int]]            
perm _ [] = [[]]
perm x list = concat [map (e:) (perm (x+1) (delete e list)) |
                                       e <- list, e /= (x+1)]
```
It’s sometimes surprising how having less can 1) be more work and 2) feel like such an achievement.
October 13, 2009
Expat Reflections

There are many things I love about Canada, but as it’s now October I should warn you: winter is not one of them. It’s so cold here that going outside feels potentially fatal. Of course, last winter (my first) was particularly bad as the result of certain situations and the 51 day bus strike (which of course was longer, because after that long they had a big maintenance backlog).

At this time of year I start to think fondly of Scotland where, no, it is not that cold (Brits say it’s cold, but after experiencing Canadian cold I can tell you we are not talking the same language of temperature) and you rarely see snow. The one time there was snow, everything ground to a halt and my Smart Car did a good impression of an ice cube.

So it’s a good time for me to be reminded of why I left the UK. The restriction of a newpaper to report (now lifted) and the news that the UK is the worse place to live in Europe. The fact that our Prime Minister did not face a vote within his party and has been in power now for over 2 years without leading his party to a general election (and has another year before he has to call one) is another good one, as is the level of national debt.

So – thanks for having me Canada. Despite the weather, I think it’s a real improvement. Just have to maintain this feeling until next April…

Snow in Edinburgh, 2007

Snow in Ottawa, 2008

October 13, 2009
Week in Brief
Goals for this week were:
- Finish coding current mini-project
- Write more on thesis, get to the point where papers can be integrated
- Finish Combinatorial Algorithms assignment
- Meet with CA prof to talk about project
- Read 4 papers
- Read thesis – “Networking in Everyday Life”
- 2 blog posts
- Portfolio website – add all pages and finish home page – decided to leave this until I get a new laptop
- Write overview for soon to be announced WISE project
- Write blog post for project
I also:
- Watched as my graphs went slightly viral! See this link to see how many times they were tweeted.
- Made a whole lot of graphs for people who wanted them!
- Claimed my blog on Technorati.
- Started using Wave for collaboration (my invites came though! Yay!)
My traffic graph is shown below. Wow! This is just my research blog – I never imagined it would ever be this popular!

For next week:
- Next Twitter Visualization (super excited about this)
- CA Project outline
- Read 5 papers
- Marking :'(
- Move ToDo Lists over to Remember The Milk
- Write more on thesis, get to the point where papers can be integrated
- Write survey for other project (more soon!)
- 3 blog posts
October 12, 2009
What Constitutes Spam on Twitter?

I don’t know if this is particularly harsh, but I consider anyone who regularly promotes the same website without declaring an affiliation to be a spammer. Sometimes a well-disguised spammer, kudos to that, but a spammer nevertheless. Note – this doesn’t include people promoting their blog on Twitter. I tweet posts from my blog that I consider to be particularly important, but by no means all. I figure if people were that interested, they’d be subscribing to my RSS feed. But I digress.

Yesterday I was followed by @emmily67. As of now is following 2,001 and has 1,222 followers. She’s tweeting amusing little things like “Marriage is a relationship in which one person is always right, and the other is a husband.“, and “Life would be easier if you could mark people as spam“. Four of her links are the same site as the one in her bio, though, and some of the amusing phrases seemed to be running on repeat. So I, ah, marked her as spam.

However I’m interested in these kinds of Twitter users because I want to graph them (if you have any examples of this, let me know). So here’s hers:

What do you think? Does this constitute spam? Or is it legitimate albeit self-promoting?

October 12, 2009
Collaborating on Google Wave

People are surprised by this, but there was a period that I checked my email just once a week a la Tim Ferris (Amazon). This was during my gap year when I was working and although it annoyed various people – my boss, a guy I worked with, some of my friends… I didn’t have a cellphone and had temporarily quit Facebook as well, so to be fair it was fairly difficult to get hold of me. However, I found myself to be much more productive. I missed email, but realized it’s a displacement activity. I check my email between tasks, before tasks, during tasks when I’m bored or distracted.

Since I went back to university checking my email once a week has become impossible. Worse, though, even checking it once a day is infeasible because I’ve been using email as a collaboration tool, and it’s just not something it does well. I’ve tried to move to Google Docs, but that just means that I create a document, alert people I’m collaborating with by email, and wait. Sometimes I have to email a reminder to get them to look at it and then I’m checking my email – and my Google Docs account. Then maybe we discuss what we’re working on via email, even if the thing we’re working on is in Google Docs. In the worse case, the only thing saved is keeping the working document up to date.

I got my Wave invite early on, and when I used my invitations my priority was to invite people I collaborate with, whether that’s for socializing, WISE, or academically (my supervisor got one, for example – we’re ditching email for Wave). The invites finally came through and I’ve now had my first “Wave collaboration experience” and it was awesome. I have to write an outline/blog post for a project we’re working on. I added our VP communications to the Wave and wrote it, then she came in and made some corrections. Underneath the section we were editing, we had a short conversation about what we were working on.

Then, well, I cut and paste what we’d produced into an email because the other person who needs this isn’t yet on Wave. But still – significant improvement.

Screenshot below:

This is awesome; it’s what I hoped Wave would be good for and I’m finally starting to experience it. I don’t see it replacing email, but I hope that once more of my friends and the people who I work with are on Wave I can replace email with Wave to communicate with them, and email will be reserved for more formal things that I don’t want to be real-time, like university notifications, inquiries from students and job hunting – and I can cut back on checking it, perhaps to once a day? That would be nice!

I am out of invites – please don’t ask me for one.

October 12, 2009
Twitter Graphs…cont

@RebekahHarriman:

@RebekahHarriman's Twitter Conversation Network

@RossIGrant:

@RossIGrant's Twitter Conversation Network

@ponkey_60 – this one is interesting because usually she protects her tweets. She unprotected them for me so I could create the graph. I wonder if people with protected tweets typically have smaller networks?

@ponkey_60's Twitter Conversation Network

@douglasgresham:

@douglasgresham's Twitter Conversation Network

@tgrevatt is having a lot of conversations!! With a lot of people who have a lot of conversations. This graph is fairly densely connected (next step is to be able to pull these networks out). There are a few purple links, which are likely to indicate things like ReTweets.

@tgrevatt's Twitter Conversation Network

@matthewfelgate:

@matthewfelgate's Twitter Conversation Network

October 12, 2009

Efficiency

At the moment, I’m taking a class in Combinatorial Algorithms. You can probably gather from the things that I write about here that this is not my passion… however so far it’s better than expected. We’re moving onto backtracking. If you know a functional language such as Haskell or ML (I know there are others, these are just the two I know) backtracking is fairly easy, so of course I ask if we can use such a functional language for our assignment. So then this exchange happens (of course I Twittered it):

Student: Why are you talking about functional programming?

Professor: Oh… she’s European.

Ah yes, we Europeans like to sit in cafe’s drinking espresso and talking about politics, philosophy, functional programming…

For our current assignment, one of the questions was to write a program that would produce all the “derangements” for a given number: a derangement is like a permutation except none of the elements are in the original position (see the table at the end of the post). There are fewer than 6 students in the class and two of them mentioned to me that they found this question difficult. However I wrote it in Haskell, and it took me 8 lines of code and 2 hours (the first chunk of which was spent getting to grips with the syntax again – it’s been a while) and runs really fast. See below:

Note – I’m not concerned about putting this up before I’ve handed it in, as there are very few students in the class and I’m confident none of the others know Haskell

-- Cate Huston - Question 3

import Data.List

derange :: Int -> [[Int]]
derange n = iter (n-1) (permutations (makeList n))

makeList :: Int -> [Int]
makeList 0 = []
makeList n = makeList (n-1) ++ [n]

iter :: Int -> [[Int]] -> [[Int]]
iter 0 ls = remove 0 ls
iter a ls = iter (a-1) (remove a ls)

remove :: Int -> [[Int]] -> [[Int]]
remove _ [] = []
remove a (l:ls) = if (l!!(a) == (a+1)) then remove a ls
                  else l : (remove a ls)

This code is efficient, in the sense that it didn’t take me very long, but it’s also very efficient to run because of the way Haskell uses lazy evaluation, so things are not created (or computed) until it’s necessary. So even though it looks, for instance, that creating a list of permutations is one of the first things I’m doing, in practice it’s something that happens very shortly before the relevant permutation does (or doesn’t) appear on my screen.

Computer Science (or Informatics) at the University of Edinburgh wasn’t always the most fun experience but here’s what I’m grateful for: I’ve programmed in 9 languages. And whilst I’m not particularly confident in all of them, I know enough about each of them to have an appreciation for when it’s appropriate. I think Haskell is most appropriate in this instance, for example, but I’m using Java for my visualizations. If I need to script something, I’ll probably use Python and I understand why C is still used a lot, but also why it’s difficult to code in (and so very, very difficult to teach a beginner). The only thing I still don’t get is Tcl (everything’s a String! Everything! Why?).

This makes me more efficient as a programmer, in that I have more choice to fine the best language for what I’m doing, and also in that I’m not afraid to learn another language and I don’t get fazed by the syntax being different. Yesterday, for example, I debugged someone’s Visual Basic code. I’ve not really done any VB before (since 2004 I’ve only used Windows when someone’s paid me to), but type errors are type errors so it didn’t take long to fix.

Programmers – we need to stop clinging to the one language we know (primarily Java, I’ve found) and thinking we can do everything in it. It’s probably possible, but there might be a better way. And in 10 years time, will Java still be this popular or will something have surpassed it? We need to have the skills to move on, if the need arises.

Derangements – all of these (and 7 – not shown) ran in well under 1s

1	[]
2	[2,1]
3	[2,3,1],[3,1,2]
4	[4,3,2,1],[3,4,2,1],[2,3,4,1],[4,1,2,3],[2,4,1,3],[2,1,4,3],[4,3,1,2],[3,4,1,2],[3,1,4,2]
5	[4,3,5,2,1],[4,3,2,5,1],[5,3,4,2,1],[3,5,4,2,1],[3,4,5,2,1],[3,4,2,5,1],[2,3,4,5,1],[2,5,4,3,1],[2,4,5,3,1],[5,4,2,3,1],[4,5,2,3,1],[5,1,2,3,4],[2,5,1,3,4],[2,1,5,3,4],[2,3,5,1,4],[2,3,1,5,4],[5,3,1,2,4],[3,5,1,2,4],[3,1,5,2,4],[3,1,2,5,4],[5,3,2,1,4],[3,5,2,1,4],[5,1,4,3,2],[5,4,1,3,2],[4,5,1,3,2],[4,1,5,3,2],[4,3,5,1,2],[4,3,1,5,2],[3,1,4,5,2],[5,3,4,1,2],[3,5,4,1,2],[3,4,5,1,2],[3,4,1,5,2],[5,1,4,2,3],[5,4,1,2,3],[4,5,1,2,3],[4,1,5,2,3],[4,1,2,5,3],[5,4,2,1,3],[4,5,2,1,3],[2,1,4,5,3],[2,5,4,1,3],[2,4,5,1,3],[2,4,1,5,3]
6	[6,5,4,3,2,1],[5,6,4,3,2,1],[5,4,6,3,2,1],[6,4,5,3,2,1],[4,6,5,3,2,1],[4,5,6,3,2,1],[6,3,4,5,2,1],[3,6,4,5,2,1],[3,4,6,5,2,1],[3,4,5,6,2,1],[3,4,5,2,6,1],[4,3,6,5,2,1],[4,3,5,6,2,1],[4,3,5,2,6,1],[3,5,4,6,2,1],[3,5,4,2,6,1],[5,3,4,6,2,1],[5,3,4,2,6,1],[2,3,4,5,6,1],[3,4,2,5,6,1],[4,3,2,5,6,1],[2,5,4,6,3,1],[2,5,4,3,6,1],[6,5,4,2,3,1],[5,6,4,2,3,1],[5,4,6,2,3,1],[5,4,2,6,3,1],[5,4,2,3,6,1],[2,6,4,5,3,1],[2,4,6,5,3,1],[2,4,5,6,3,1],[2,4,5,3,6,1],[6,4,2,5,3,1],[4,6,2,5,3,1],[6,4,5,2,3,1],[4,6,5,2,3,1],[4,5,6,2,3,1],[4,5,2,6,3,1],[4,5,2,3,6,1],[2,6,5,3,4,1],[2,5,6,3,4,1],[6,5,2,3,4,1],[5,6,2,3,4,1],[5,3,6,2,4,1],[5,3,2,6,4,1],[2,3,6,5,4,1],[2,3,5,6,4,1],[6,3,2,5,4,1],[3,6,2,5,4,1],[6,3,5,2,4,1],[3,6,5,2,4,1],[3,5,6,2,4,1],[3,5,2,6,4,1],[6,1,2,3,4,5],[2,6,1,3,4,5],[2,1,6,3,4,5],[2,3,6,1,4,5],[2,3,1,6,4,5],[2,3,4,6,1,5],[2,3,4,1,6,5],[6,3,1,2,4,5],[3,6,1,2,4,5],[3,1,6,2,4,5],[3,1,2,6,4,5],[6,3,2,1,4,5],[3,6,2,1,4,5],[6,1,4,3,2,5],[6,4,1,3,2,5],[4,6,1,3,2,5],[4,1,6,3,2,5],[4,3,6,1,2,5],[4,3,1,6,2,5],[4,3,1,2,6,5],[4,3,6,2,1,5],[4,3,2,6,1,5],[4,3,2,1,6,5],[3,1,4,6,2,5],[3,1,4,2,6,5],[6,3,4,1,2,5],[3,6,4,1,2,5],[3,4,6,1,2,5],[3,4,1,6,2,5],[3,4,1,2,6,5],[6,3,4,2,1,5],[3,6,4,2,1,5],[3,4,6,2,1,5],[3,4,2,6,1,5],[3,4,2,1,6,5],[6,1,4,2,3,5],[6,4,1,2,3,5],[4,6,1,2,3,5],[4,1,6,2,3,5],[4,1,2,6,3,5],[4,1,2,3,6,5],[6,4,2,1,3,5],[4,6,2,1,3,5],[6,4,2,3,1,5],[4,6,2,3,1,5],[2,1,4,6,3,5],[2,1,4,3,6,5],[2,6,4,1,3,5],[2,4,6,1,3,5],[2,4,1,6,3,5],[2,4,1,3,6,5],[2,6,4,3,1,5],[2,4,6,3,1,5],[5,1,4,6,3,2],[5,1,4,3,6,2],[6,5,4,1,3,2],[5,6,4,1,3,2],[5,4,6,1,3,2],[5,4,1,6,3,2],[5,4,1,3,6,2],[6,5,4,3,1,2],[5,6,4,3,1,2],[5,4,6,3,1,2],[6,1,4,5,3,2],[6,4,1,5,3,2],[4,6,1,5,3,2],[4,1,6,5,3,2],[4,1,5,6,3,2],[4,1,5,3,6,2],[6,4,5,1,3,2],[4,6,5,1,3,2],[4,5,6,1,3,2],[4,5,1,6,3,2],[4,5,1,3,6,2],[6,4,5,3,1,2],[4,6,5,3,1,2],[4,5,6,3,1,2],[4,3,1,5,6,2],[4,3,6,5,1,2],[4,3,5,6,1,2],[4,3,5,1,6,2],[6,1,5,3,4,2],[6,5,1,3,4,2],[5,6,1,3,4,2],[5,1,6,3,4,2],[5,3,6,1,4,2],[5,3,1,6,4,2],[5,3,4,6,1,2],[5,3,4,1,6,2],[6,3,1,5,4,2],[3,6,1,5,4,2],[3,1,6,5,4,2],[3,1,5,6,4,2],[6,3,5,1,4,2],[3,6,5,1,4,2],[3,5,6,1,4,2],[3,5,1,6,4,2],[3,5,4,6,1,2],[3,5,4,1,6,2],[3,1,4,5,6,2],[3,4,1,5,6,2],[6,3,4,5,1,2],[3,6,4,5,1,2],[3,4,6,5,1,2],[3,4,5,6,1,2],[3,4,5,1,6,2],[6,1,5,2,3,4],[6,5,1,2,3,4],[5,6,1,2,3,4],[5,1,6,2,3,4],[5,1,2,6,3,4],[5,1,2,3,6,4],[6,5,2,1,3,4],[5,6,2,1,3,4],[6,5,2,3,1,4],[5,6,2,3,1,4],[6,1,2,5,3,4],[2,6,1,5,3,4],[2,1,6,5,3,4],[2,1,5,6,3,4],[2,1,5,3,6,4],[2,6,5,1,3,4],[2,5,6,1,3,4],[2,5,1,6,3,4],[2,5,1,3,6,4],[2,6,5,3,1,4],[2,5,6,3,1,4],[2,3,1,5,6,4],[2,3,6,5,1,4],[2,3,5,6,1,4],[2,3,5,1,6,4],[6,1,5,3,2,4],[6,5,1,3,2,4],[5,6,1,3,2,4],[5,1,6,3,2,4],[5,3,6,1,2,4],[5,3,1,6,2,4],[5,3,1,2,6,4],[5,3,6,2,1,4],[5,3,2,6,1,4],[5,3,2,1,6,4],[6,3,1,5,2,4],[3,6,1,5,2,4],[3,1,6,5,2,4],[3,1,5,6,2,4],[3,1,5,2,6,4],[6,3,5,1,2,4],[3,6,5,1,2,4],[3,5,6,1,2,4],[3,5,1,6,2,4],[3,5,1,2,6,4],[6,3,5,2,1,4],[3,6,5,2,1,4],[3,5,6,2,1,4],[3,5,2,6,1,4],[3,5,2,1,6,4],[3,1,2,5,6,4],[6,3,2,5,1,4],[3,6,2,5,1,4],[6,1,5,2,4,3],[6,5,1,2,4,3],[5,6,1,2,4,3],[5,1,6,2,4,3],[5,1,2,6,4,3],[6,5,2,1,4,3],[5,6,2,1,4,3],[6,1,2,5,4,3],[2,6,1,5,4,3],[2,1,6,5,4,3],[2,1,5,6,4,3],[2,6,5,1,4,3],[2,5,6,1,4,3],[2,5,1,6,4,3],[2,5,4,6,1,3],[2,5,4,1,6,3],[2,1,4,5,6,3],[2,4,1,5,6,3],[2,6,4,5,1,3],[2,4,6,5,1,3],[2,4,5,6,1,3],[2,4,5,1,6,3],[5,1,4,6,2,3],[5,1,4,2,6,3],[6,5,4,1,2,3],[5,6,4,1,2,3],[5,4,6,1,2,3],[5,4,1,6,2,3],[5,4,1,2,6,3],[6,5,4,2,1,3],[5,6,4,2,1,3],[5,4,6,2,1,3],[5,4,2,6,1,3],[5,4,2,1,6,3],[6,1,4,5,2,3],[6,4,1,5,2,3],[4,6,1,5,2,3],[4,1,6,5,2,3],[4,1,5,6,2,3],[4,1,5,2,6,3],[6,4,5,1,2,3],[4,6,5,1,2,3],[4,5,6,1,2,3],[4,5,1,6,2,3],[4,5,1,2,6,3],[6,4,5,2,1,3],[4,6,5,2,1,3],[4,5,6,2,1,3],[4,5,2,6,1,3],[4,5,2,1,6,3],[4,1,2,5,6,3],[6,4,2,5,1,3],[4,6,2,5,1,3]

October 11, 2009

Do Twitter Scammers Have Conversations?

I’d like to say a big thankyou to @CoureyGetsMoney for following me (3,109 Following 2,831 Followers). His bio reads:

Thanks for checking out my page im a real cool guy making 12,000 a month working from home with GDI

I suspect he’s lying about his income and about being a “real cool guy”. I also suspect he’s using auto-follow and is just trying to drive traffic to his scam. Lets check out his graph…

He’s not part of the conversation. Just a scammer. Spammer. Whatever. What does your graph say about you?

October 10, 2009
Visualizing your Twitter Conversations: Rationale

I’ve frankly been amazed by the number of hits I’ve had on my Twitter Graphs since I put them up yesterday. This is the first phase of something I’m working on, so I’m going to write a little about the logic behind it here. Suggestions or thoughts are very welcome!

There was a time when follower counts meant something on Twitter. But that was probably before spammers, auto-follow (interesting article on how spammers and auto-follow have ruined the “social contract), and Robert Scoble‘s much hated “recommended list” (interesting post listing other people to follow who aren’t on the recommended list here). Now I think that looking at the number of people someone follows is a poor measure of their level of engagement with Twitter. Because I think a lot of what makes Twitter great is conversations it’s more interesting to me to measure those instead.

To clarify – the graphs I’ve done have mostly gone to a depth of 1, which means that it graphs the central user (checks their last 200 tweets for people they’ve mentioned, and the last 100 tweets that have mentioned them), and then does the same thing for everyone they’ve mentioned or who has mentioned them, but goes no further (I am aware of the flaws in this, fix coming soon). This means that there could well be (and likely are) connections between second degree nodes from the center person, which aren’t shown. The application doesn’t use verification, so people with protected tweets will seem to have only one way relationships because any mentions they’ve made will not show up.

Here’s my graph, below:

The yellow lines indicate a reciprocal relationship. Purple and red are one way relationships. It’s not always clear which direction it is in, but if you look at the “kittenthebad” node in the center, I mentioned “Zotero” (purple), but “unmasker” mentioned me (pink). If you look above to the left, you see my friends @zara_p and @douglasgresham and we have a little network going on there with a couple of other people we have in common. Below my node, you can see my friends @map_maker and @emdaniels and the people we have in common there too. So I think what my graph shows is that I’m primarily a conversationalist on Twitter and that most of the people I talk about, or to, I have a reciprocal relationship with. The other thing it shows, if you look at the number of people I’m following (57) is that the number of people I’m talking to is large relative to my network, about half.

Now let’s take the last person who auto-followed me based on a keyword (lolcats), (please don’t click on this link if you’re easily offended) Trollcats . As of writing this, Trollcats has 2,660 following and 5,367 followers so you’d expect them to have a huge graph, right? See below:

Their network here is much smaller, they’re having fewer conversations and the people who they’re having conversations with mostly aren’t connected to one another. This suggests that they’re less engaged, and are using Twitter as more of a broadcast medium. However if they were getting ReTweeted a lot, their graph would look different. Remember @snookca (his graph is here). He has around twice as many followers, but his graph is exponentially more crazy – because he’s engaged with Twitter and having conversations.

For a big broadcaster, see @guardiantech below – they’re not having a lot of conversations on Twitter but a lot of people are talking to or about them – likely they’re getting a lot more ReTweets:

So why is this useful, or interesting? This is fairly new, so I can’t be sure yet but here’s what I think we’ll find. I think that graphs will be different, depending on how people use Twitter. Conversationalists, spammers, the uber-popular will have distinct patterns. I think that visualizing your network will show you sub-networks that may be surprising, and get a measure of how many sub-networks you’re a part of (the next step of this is – what are these subnetworks talking about?), and will also show which of your friends are “Twitter Connectors” (people who are in a lot of sub-networks). And I think as a result of this, visualizing someone who’s followed you will tell you a lot about whether you want to follow them back. Are they a spammer? Are they just broadcasting? How engaged are they relative to the number of people they’re following – if very, they’re likely following you because they want to strike up a conversation. If not much, they may just be following you in the hope you follow them back.

This is written in Java and if you have some knowledge of programming and can run Eclipse it’s relatively easy to set up and run yourself. The source code is still being worked on, but I can make it available as-is to anyone who’s interested in running it.

October 9, 2009