CODEWITHSUNDEEP
haskellrecursion
K.Boyette
K.Boyette

Reputation: 343

Haskell: Transposition on a list of strings

New to Haskell and the language has been fun so far. I am hoping for a good hint rather than an answer as I am enjoying the mind-altering that is Haskell.

Question: I have a list of strings and I would like to transpose them. 

let x = ["hello", "world"]

would become 

["hw", "eo", "lr", "ll", "od"]

What I have so far is this: 

   transposeString :: [a] -> [a]
   transposeString ([]:_) = []
   transposeString x = (map head x) : transposeString (map tail x)

I definitely know there is something wrong with the type signature. My rational is that 

Let y = ["wow", "top"]
map head y

returns "wt" so recursing this on the rest of the list would work?

Thank you in advance for any hints.

Upvotes: 1

Views: 1712

Answers (3)

Sergey Luchko
Sergey Luchko

Reputation: 3346

Do remember String is [Char]

"abc" == 'a' : 'b' : 'c' : []

From here you can use traversable nature of lists:

transpose :: [[a]] -> [[a]]
transpose mat = getZipList $ sequenceA $ map ZipList mat

test' = transpose [[1,2,3],[4,5,6],[7,8,9]] -- == [[1,4,7],[2,5,8],[3,6,9]]
test'' = transpose ["abc", "deg", "klm"] -- == ["adk","bel","cgm"]

You can also check default implementation of transponse in haskell doc https://hackage.haskell.org/package/base-4.12.0.0/docs/src/Data.OldList.html#transpose

transpose               :: [[a]] -> [[a]]
transpose []             = []
transpose ([]   : xss)   = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477180

Mind that you do not have to provide a type signature: the Haskell compiler can derive one. If you put your implementation in a file:

transposeString ([]:_) = []
transposeString x = (map head x) : transposeString (map tail x)

and query the type with :t in ghci, it returns:

*Main> :t transposeString 
transposeString :: [[b]] -> [[b]]

This makes perfect sense:

  1. you transpose a matrix, which is a list of lists. [[b]] is a list of lists of b elements; and
  2. you can derive it from the implementation yourself: map head x means that elements of x must be a list ([b]) since we perform a mapping, we have to nest the list one additional level so [[b]]. The same for tail.

As far as I know, your implementation is correctly. You can specialize it by saying that [b] ~ String, thus adding a type signature for Strings:

transposeString :: [String] -> [String]
transposeString ([]:_) = []
transposeString x = (map head x) : transposeString (map tail x)

which again makes sense because String ~ [Char] thus b ~ Char. But there is not much point in specializing a functions type: you better always use the most generic type signature. In this case [[b]] -> [[b]].

Upvotes: 4

Kwarrtz
Kwarrtz

Reputation: 2753

One point of note. Your type signature for tranposeString allows to accept a flat list as an argument. Tranposing a [String] works because [String]s are really just [[Char]]s, but what happens when you try to call transposeString on an [Int]? After all, the type signature allows for it.

On a side note, I ask you, given your current function, what would happen if your called transposeString []?

Upvotes: 2

Related Questions