Skip to main content
2 de 4
se añadieron 177 caracteres en el cuerpo

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