Merging an infinite list of infinite lists

A paper I was reading today for class contained a problem that I thought was interesting: How do you merge an infinite list of infinite lists such that every element in the list is indexable? The paper introduced a monadic solution using faux-concurrency that was pretty cute, but it got me thinking about a simpler solution.

In an effort to maintain my nerd credentials after my spate of sports posts, I figured I'd throw my code up here and call it content. This is the sort of stuff I procrastinate with all the time, so if anyone's interested in mostly useless snippets of Haskell code, maybe I'll do this more regularly.

merge :: [[a]] -> [a]
merge ls = [ls !! x !! y | (x,y) <- p 0 0]
  where p 0 y = (0,y) : p (y+1) 0
        p x y = (x,y) : p (x-1) (y+1)

Pretty simple. p generates all pairs (x,y) in the order of the Cantor pairing function. x and y indicate which list, and which value in that list to return next.

An example application of this function in GHCi:

> take 10 $ merge [[i..] | i <- [100,200..]]
[100,200,101,300,201,102,400,301,202,103]

Super Sports Mega Post

Alright, so it's only two subtopics, but at my current pace, anything more than zero should qualify for "mega post" status.


MLB 2009 Standings Predictions

First up, my final standings predictions for this year's major league baseball season. I've done this in email form many times in the past, but with my fan blog practically pounding down my door, demanding content, I figured I'd throw it on my blog instead. Make sure to bookmark it and come back in nine months so you can ridicule me for failing to predict the Pittsburgh Pirates' breakthrough season.

Proceeding through the leagues alphabetically and across the country from left to right:

AL West
Los Angeles
Oakland
Seattle
Texas

I went into this division trying to justify a ranking that went something like: Seattle, Oakland, Los Angeles, Texas, but just couldn't make it work. Even with the injuries to their starting rotation, and even without Teixeira, the Angels are still the best team in the AL West. This is the worst division in baseball, however, and with a few breaks any team could win it--the standings after the Angels give the relative likelihood of each team catching those breaks. Fortunately, the division is on the upswing. The A's and Rangers are loaded with young talent, and the M's finally have someone in charge who can make the most of their significant resources.

AL Central
Cleveland
Detroit
Minnesota
Chicago
Kansas City

The defending division champion White Sox pretty consistently outperform my expectations, but I just look at that roster and don't see any way they're better than the three teams I put ahead of them. If the Tigers once-promising young starters finally put it together, they could pull out an upset, but otherwise Grady Sizemore and Cleveland's impressive depth are the clear favorites.

AL East
Boston
Tampa Bay (wild card winner)
New York
Toronto
Baltimore

This division is absolutely stacked. The top three teams here would win any other division in baseball without much of a contest, and one of them won't make the playoffs... The Yankees look the best on paper, but with A-Rod out to start the season and enough aging veterans elsewhere, I feel justified in placing them third. Perhaps it's just wishful thinking. It's got to be a real bummer to be a fan of the solid Blue Jays or up-and-coming Orioles right now, because despite being perfectly respectable teams, they have no chance for the foreseeable future.

NL West
Arizona
Los Angeles
San Francisco
Colorado
San Diego

Both the Dodgers and Diamondbacks have excellent young cores and look like they should finish first and second in this division for the next few years. I like the D-Backs a bit better since they seem to have just a little more upside and a little less risk. The Giants seem to have gone from terrible to respectable very quickly, mostly thanks to their outstanding starting pitching; unfortunately for them this is balanced by a thoroughly anemic offense.

NL Central
Milwaukee
Chicago (wild card winner)
St. Louis
Cincinnati
Houston
Pittsburgh

By all accounts, the Cubs are the team to beat in the Central. So why do I pick the Brewers? Because I always pick the Brewers, and I sure don't plan on being wrong when they finally do win the division. The Brewers and Cubs are both great teams and whoever doesn't win the division is going to be competing with two teams in the NL East for the wildcard. The Cardinals are almost entirely the Albert Pujols show at this point (but what a show!), but if the Chris Carpenter come back goes as planned, they could be in the mix as well. The Pirates, on the other hand, are the early favorites for worst team in baseball.

NL East
New York
Philadelphia
Atlanta
Florida
Washington

I think I might be the biggest Jeff Francoeur believer left on the planet, but try as I might, I just couldn't figure out a way to get the Braves into the playoffs. Their pitching staff is outstanding and Chipper Jones is a Hall of Famer who's still raking in his late 30's, but there are just too many weak spots on this roster, and especially so when Chipper's out for an extended stretch, as he is every year. The Mets and Phillies both have their flaws, of course, but they've both got enough star power to make up for them. The Marlins have a lot of upside and the Nationals are bad (hurray!).


Ranking the Blazers

During halftime of the Blazers-Jazz game the other day, I cajoled Chris and Tim into ranking the Blazers with me. These rankings are based simply on how much we like each player, and we only included the 11 players who get semi-regular playing time or more. The Blazers are currently just about the most likeable sports team, top-to-bottom in the history of the world, so this was no easy task.

I suppose I'll spare you the actual lists, but here's an awesome graph Chris made from which they can be derived. The x-axis is the players, obviously, sorted by their average ranking. The y-axis is their ranking on each of our lists, 1 being our most favorite players, 11 being our least favorite.