Search code examples
listhaskelltypestuplestype-mismatch

Haskell - indexing a list

I have a list of 3 tuples items, I would like to index the list based on the first item, I have already written a code that sounds logically sane to me yet am getting a type error, here's what I wrote

addIndex [] indexed = indexed
addIndex ((a1,b1,c1):xs) [] 
                    = addIndex xs [(a1,b1,c1,0)]
addIndex ((a1,b1,c1):xs) indexedWIP 
                    = addIndexH ((a1,b1,c1):xs) indexedWIP (last indexedWIP)
addIndexH ((a1,b1,c1):xs) indexedWIP (ax,bx,cx,ix)
                    = if (a1 /= ax) 
                        then (addIndex xs (indexedWIP ++ (a1,b1,c1,(ix+1)))) 
                        else (addIndex xs (indexedWIP ++ (a1,b1,c1,(ix))))

I'm getting the following type error

ERROR file:.\lmaogetrektson.hs:109 - Type error in application
*** Expression     : indexedWIP ++ (a1,b1,c1,ix + 1)
*** Term           : (a1,b1,c1,ix + 1)
*** Type           : (b,c,d,e)
*** Does not match : [a]
Solution

  • Let me examine the types of your addIndex at each row:

    addIndex :: [a] -> b -> b
addIndex [] indexed = indexed

-- Combined with the above, leads to:
addIndex :: (Num n) => [(a,b,c)] -> [(a,b,c,n)] -> [(a,b,c,n)]
addIndex ((a1,b1,c1):xs) [] = addIndex xs [(a1,b1,c1,0)]

-- This call demands addIndexH satisfies:
addIndexH :: (Num n) => [(a,b,c)] -> [(a,b,c,n)] -> (a,b,c,n) -> [(a,b,c,n)]
-- It's also costly, as last needs to traverse the list
addIndex ((a1,b1,c1):xs) indexedWIP = 
    addIndexH ((a1,b1,c1):xs) indexedWIP (last indexedWIP)

-- /= check matches types of a1 and ax, requiring them to be Eq
addIndexH ((a1,b1,c1):xs) indexedWIP (ax,bx,cx,ix) = 
    if (a1 /= ax) then (addIndex xs (indexedWIP ++ (a1,b1,c1,(ix+1)))) 
    else (addIndex xs (indexedWIP ++ (a1,b1,c1,(ix))))

    The distinction of list and tuple is actually the problem you hit here. 

    Prelude> :t (++)
(++) :: [a] -> [a] -> [a]

    Both operands to ++ must be same-type lists. So we need something like:

    addIndexH ((a1,b1,c1):xs) indexedWIP (ax,bx,cx,ix) = 
    if (a1 /= ax) then (addIndex xs (indexedWIP ++ [(a1,b1,c1,(ix+1))])) 
    else (addIndex xs (indexedWIP ++ [(a1,b1,c1,(ix))]))

    The end result should be a function that takes a list of 3-tuples and another list of enumerated 4-tuples, but in a rather circuitous manner. Consider how it expands:

    addIndex [(a,b,c), (x,y,z)] []
addIndex [(x,y,z)] [(a,b,c,0)]
addIndexH [(x,y,z)] [(a,b,c,0)] (a,b,c,0)
addIndex [] ([(a,b,c,0)] ++ [(x,y,z,(0+1))])
([(a,b,c,0)] ++ [(x,y,z,(0+1))])

    That's a fairly complex procedure, and it grows worse the longer the lists are (we haven't even looked at duplicate a fields yet).

    When you do encounter a duplicate a field, you still append it, only keeping the new index value. This means, since we only checked against the last item, that we have two items of matching a and index right next to each other. The function could be rewritten in several ways, in particular without rebuilding lists of every intermediate length and traversing the growing one for each element.