9 May
                
                    2008
                
            
            
                9 May
                
                '08
                
            
            
            
        
    
                10:16 a.m.
            
        The function (++) :: [x] -> [x] -> [x] has O(n) complexity. If somebody were to invent some type that looks like [x] but actually uses some sort of tree rather than a linked list, you should be able to get O(1) concatenation. Has anybody ever implemented such a thing?