El problema de tu implementación es que estás concatenando cada dígito al final de la lista en cada iteración. El operador ++
tiene un coste lineal respecto al número de elementos de la primera lista. Por tanto, si el número binario resultante tiene n
dígitos, tu implementación hace (n-1) + (n-2) + (n-3) + ... + (n-n)
iteraciones para construir la lista final, cuya progresión es igual a (n-1)*n/2
, que resulta ser un orden de complejidad cuadrático respecto al número de dígitos del número binario.
Lo más común es construir la lista al revés (encabezando los elementos con :
), y darle la vuelta al final con reverse
en una única pasada. El operador :
es el constructor de listas, que toma un elemento x
y una lista xs
y devuelve (en tiempo constante) la lista x:xs
con cabeza x
y cola xs
. La función reverse
invierte una lista en tiempo lineal, por lo tanto la función resultante tiene un orden de complejidad lineal respecto al número de dígitos del número binario:
toBin, auxBin :: Int -> [Int]
toBin 0 = [0]
toBin n = reverse (auxBin n)
auxBin 0 = []
auxBin n = n `mod` 2 : auxBin (n `div` 2)
Para contar el número de 1
de la lista resultante, puedes filtrar los elementos iguales a 1
con la función filter
, y luego calcular la longitud con la función length
:
ghci> filter (==1) [1,0,0,1,1]
[1,1,1]
ghci> length (filter (==1) [1,0,0,1,1])
3
Combinándolo con toBin
en una función:
countOnes :: Int -> Int
countOnes = length . (filter (==1)) . toBin