How to deal with recursing through a list in Haskell (transpose operation)





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}







1















While I understand that there may be transpose or ZipList functions in Haskell, I am trying to build my own transpose function that will take n lists of equal length m and transpose them into m lists of length n.



So far I have the function nearly working with the following code:



list = [[1,2,3],[4,5,6],[7,8,9]]



head' (x:xs) = x



head''  = 

head'' (xs:lxs) = head' xs:head'' lxs



tail'  = 

tail' (x:xs) = xs



tail''  = 

tail'' (xs:lxs) = tail' xs:tail'' lxs



merge (xs:lxs) = (head' xs:head'' lxs):(merge (tail' xs:tail'' lxs))


and I get the following output when I run > merge list in ghci I get:



[[1,4,7],[2,5,8],[3,6,9],[*** Exception: list2.hs:16:1-16: Non-exhaustive patterns in function head'


which I am pretty sure means that the base case of the empty list on my head' function is missing. The list is transposed, just not closed. How do I deal with that problem in this case? I have an inkling that it might have to do with Maybe, but I'm having trouble implementing it that way.






list haskell recursion transpose non-exhaustive-patterns







share|improve this question




















  • 6





    head' (x:xs) = x, but what is head' ?

    – Adam Smith
    Jan 4 at 9:14






  • 1





    Since head' xs:head'' lxs = head'' (xs:lxs), you can collapse merge (xs:lxs) = (head' xs:head'' lxs):... to merge (xs:lxs) = (head'' (xs:lxs)):.... Similar equational reasoning applies to the ..., giving merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). At that point there's not much point to pattern matching; merge lxs = head'' lxs:tail'' lxs. But now you should definitely be suspicious: this definition of merge obviously always calls (:) and never . So how does one get to the "end" of the merge's output?

    – Daniel Wagner
    Jan 4 at 18:13




















1















While I understand that there may be transpose or ZipList functions in Haskell, I am trying to build my own transpose function that will take n lists of equal length m and transpose them into m lists of length n.



So far I have the function nearly working with the following code:



list = [[1,2,3],[4,5,6],[7,8,9]]



head' (x:xs) = x



head''  = 

head'' (xs:lxs) = head' xs:head'' lxs



tail'  = 

tail' (x:xs) = xs



tail''  = 

tail'' (xs:lxs) = tail' xs:tail'' lxs



merge (xs:lxs) = (head' xs:head'' lxs):(merge (tail' xs:tail'' lxs))


and I get the following output when I run > merge list in ghci I get:



[[1,4,7],[2,5,8],[3,6,9],[*** Exception: list2.hs:16:1-16: Non-exhaustive patterns in function head'


which I am pretty sure means that the base case of the empty list on my head' function is missing. The list is transposed, just not closed. How do I deal with that problem in this case? I have an inkling that it might have to do with Maybe, but I'm having trouble implementing it that way.






list haskell recursion transpose non-exhaustive-patterns







share|improve this question




















  • 6





    head' (x:xs) = x, but what is head' ?

    – Adam Smith
    Jan 4 at 9:14






  • 1





    Since head' xs:head'' lxs = head'' (xs:lxs), you can collapse merge (xs:lxs) = (head' xs:head'' lxs):... to merge (xs:lxs) = (head'' (xs:lxs)):.... Similar equational reasoning applies to the ..., giving merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). At that point there's not much point to pattern matching; merge lxs = head'' lxs:tail'' lxs. But now you should definitely be suspicious: this definition of merge obviously always calls (:) and never . So how does one get to the "end" of the merge's output?

    – Daniel Wagner
    Jan 4 at 18:13
















1












1








1


0






While I understand that there may be transpose or ZipList functions in Haskell, I am trying to build my own transpose function that will take n lists of equal length m and transpose them into m lists of length n.



So far I have the function nearly working with the following code:



list = [[1,2,3],[4,5,6],[7,8,9]]



head' (x:xs) = x



head''  = 

head'' (xs:lxs) = head' xs:head'' lxs



tail'  = 

tail' (x:xs) = xs



tail''  = 

tail'' (xs:lxs) = tail' xs:tail'' lxs



merge (xs:lxs) = (head' xs:head'' lxs):(merge (tail' xs:tail'' lxs))


and I get the following output when I run > merge list in ghci I get:



[[1,4,7],[2,5,8],[3,6,9],[*** Exception: list2.hs:16:1-16: Non-exhaustive patterns in function head'


which I am pretty sure means that the base case of the empty list on my head' function is missing. The list is transposed, just not closed. How do I deal with that problem in this case? I have an inkling that it might have to do with Maybe, but I'm having trouble implementing it that way.






list haskell recursion transpose non-exhaustive-patterns







share|improve this question
















While I understand that there may be transpose or ZipList functions in Haskell, I am trying to build my own transpose function that will take n lists of equal length m and transpose them into m lists of length n.



So far I have the function nearly working with the following code:



list = [[1,2,3],[4,5,6],[7,8,9]]



head' (x:xs) = x



head''  = 

head'' (xs:lxs) = head' xs:head'' lxs



tail'  = 

tail' (x:xs) = xs



tail''  = 

tail'' (xs:lxs) = tail' xs:tail'' lxs



merge (xs:lxs) = (head' xs:head'' lxs):(merge (tail' xs:tail'' lxs))


and I get the following output when I run > merge list in ghci I get:



[[1,4,7],[2,5,8],[3,6,9],[*** Exception: list2.hs:16:1-16: Non-exhaustive patterns in function head'


which I am pretty sure means that the base case of the empty list on my head' function is missing. The list is transposed, just not closed. How do I deal with that problem in this case? I have an inkling that it might have to do with Maybe, but I'm having trouble implementing it that way.






list haskell recursion transpose non-exhaustive-patterns




list haskell recursion transpose non-exhaustive-patterns






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Jan 18 at 11:18









Will Ness

46.7k469127




46.7k469127










asked Jan 4 at 9:08









Ron FRon F

226




226








  • 6





    head' (x:xs) = x, but what is head' ?

    – Adam Smith
    Jan 4 at 9:14






  • 1





    Since head' xs:head'' lxs = head'' (xs:lxs), you can collapse merge (xs:lxs) = (head' xs:head'' lxs):... to merge (xs:lxs) = (head'' (xs:lxs)):.... Similar equational reasoning applies to the ..., giving merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). At that point there's not much point to pattern matching; merge lxs = head'' lxs:tail'' lxs. But now you should definitely be suspicious: this definition of merge obviously always calls (:) and never . So how does one get to the "end" of the merge's output?

    – Daniel Wagner
    Jan 4 at 18:13
















  • 6





    head' (x:xs) = x, but what is head' ?

    – Adam Smith
    Jan 4 at 9:14






  • 1





    Since head' xs:head'' lxs = head'' (xs:lxs), you can collapse merge (xs:lxs) = (head' xs:head'' lxs):... to merge (xs:lxs) = (head'' (xs:lxs)):.... Similar equational reasoning applies to the ..., giving merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). At that point there's not much point to pattern matching; merge lxs = head'' lxs:tail'' lxs. But now you should definitely be suspicious: this definition of merge obviously always calls (:) and never . So how does one get to the "end" of the merge's output?

    – Daniel Wagner
    Jan 4 at 18:13










6




6





head' (x:xs) = x, but what is head' ?

– Adam Smith
Jan 4 at 9:14





head' (x:xs) = x, but what is head' ?

– Adam Smith
Jan 4 at 9:14




1




1





Since head' xs:head'' lxs = head'' (xs:lxs), you can collapse merge (xs:lxs) = (head' xs:head'' lxs):... to merge (xs:lxs) = (head'' (xs:lxs)):.... Similar equational reasoning applies to the ..., giving merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). At that point there's not much point to pattern matching; merge lxs = head'' lxs:tail'' lxs. But now you should definitely be suspicious: this definition of merge obviously always calls (:) and never . So how does one get to the "end" of the merge's output?

– Daniel Wagner
Jan 4 at 18:13







Since head' xs:head'' lxs = head'' (xs:lxs), you can collapse merge (xs:lxs) = (head' xs:head'' lxs):... to merge (xs:lxs) = (head'' (xs:lxs)):.... Similar equational reasoning applies to the ..., giving merge (xs:lxs) = (head'' (xs:lxs)):(tail'' (xs:lxs)). At that point there's not much point to pattern matching; merge lxs = head'' lxs:tail'' lxs. But now you should definitely be suspicious: this definition of merge obviously always calls (:) and never . So how does one get to the "end" of the merge's output?

– Daniel Wagner
Jan 4 at 18:13














2 Answers
2






active

oldest

votes


















1














You need to add exit conditions:



merge  = 

merge (:xss) = merge xss





share|improve this answer
























  • So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

    – Ron F
    Jan 4 at 18:24



















0














map is all you need, in addition to the existing head and tail functions. For simplicity, this assumes that the input is always a non-empty list (i.e., xs might be [,,], but never alone, so there's no problem with using head or tail.)



> map head list

[1,4,7]

> map tail list

[[2,3],[5,6],[8,9]]

> let foo xs = if null (head xs) then  else map head xs : foo (map tail xs)

> foo list

[[1,4,7],[2,5,8],[3,6,9]]





share|improve this answer
























    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54035881%2fhow-to-deal-with-recursing-through-a-list-in-haskell-transpose-operation%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1














    You need to add exit conditions:



    merge  = 
    
merge (:xss) = merge xss





    share|improve this answer
























    • So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

      – Ron F
      Jan 4 at 18:24
















    1














    You need to add exit conditions:



    merge  = 
    
merge (:xss) = merge xss





    share|improve this answer
























    • So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

      – Ron F
      Jan 4 at 18:24














    1












    1








    1







    You need to add exit conditions:



    merge  = 
    
merge (:xss) = merge xss





    share|improve this answer













    You need to add exit conditions:



    merge  = 
    
merge (:xss) = merge xss






    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered Jan 4 at 9:42









    talextalex

    11.9k11749




    11.9k11749













    • So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

      – Ron F
      Jan 4 at 18:24



















    • So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

      – Ron F
      Jan 4 at 18:24

















    So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

    – Ron F
    Jan 4 at 18:24





    So when does merge (:xss) = merge xss run as opposed to the other two definitions of merge?

    – Ron F
    Jan 4 at 18:24













    0














    map is all you need, in addition to the existing head and tail functions. For simplicity, this assumes that the input is always a non-empty list (i.e., xs might be [,,], but never alone, so there's no problem with using head or tail.)



    > map head list
    
[1,4,7]
    
> map tail list
    
[[2,3],[5,6],[8,9]]
    
> let foo xs = if null (head xs) then  else map head xs : foo (map tail xs)
    
> foo list
    
[[1,4,7],[2,5,8],[3,6,9]]





    share|improve this answer




























      0














      map is all you need, in addition to the existing head and tail functions. For simplicity, this assumes that the input is always a non-empty list (i.e., xs might be [,,], but never alone, so there's no problem with using head or tail.)



      > map head list
      
[1,4,7]
      
> map tail list
      
[[2,3],[5,6],[8,9]]
      
> let foo xs = if null (head xs) then  else map head xs : foo (map tail xs)
      
> foo list
      
[[1,4,7],[2,5,8],[3,6,9]]





      share|improve this answer


























        0












        0








        0







        map is all you need, in addition to the existing head and tail functions. For simplicity, this assumes that the input is always a non-empty list (i.e., xs might be [,,], but never alone, so there's no problem with using head or tail.)



        > map head list
        
[1,4,7]
        
> map tail list
        
[[2,3],[5,6],[8,9]]
        
> let foo xs = if null (head xs) then  else map head xs : foo (map tail xs)
        
> foo list
        
[[1,4,7],[2,5,8],[3,6,9]]





        share|improve this answer













        map is all you need, in addition to the existing head and tail functions. For simplicity, this assumes that the input is always a non-empty list (i.e., xs might be [,,], but never alone, so there's no problem with using head or tail.)



        > map head list
        
[1,4,7]
        
> map tail list
        
[[2,3],[5,6],[8,9]]
        
> let foo xs = if null (head xs) then  else map head xs : foo (map tail xs)
        
> foo list
        
[[1,4,7],[2,5,8],[3,6,9]]






        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Jan 4 at 14:14









        chepnerchepner

        262k36251345




        262k36251345






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54035881%2fhow-to-deal-with-recursing-through-a-list-in-haskell-transpose-operation%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            -

            Popular posts from this blog

            Monofisismo

            Image
            Monofisismo (do grego: monos - "único, singular" e physis - "natureza") é o ponto de vista cristológico que defende que, depois da união do divino e do humano na encarnação histórica, Jesus Cristo, como encarnação do Filho ou Verbo ( Logos ) de Deus, teria apenas uma única "natureza", a divina, e não uma síntese de ambas. O monofisismo é contraposto pelo diofisismo (ou "diafisismo"), que defende que Jesus preservou em si as duas naturezas. Historicamente, o monofisismo se refere primordialmente à posição dos que (especialmente no Egito e, em menor grau, na Síria) rejeitaram as decisões do Concílio de Calcedônia em 451 (o quarto concílio ecumênico). Os membros mais moderados entre eles, porém, defendem a teologia "miafisita", que se tornou a oficial para as Igrejas Ortodoxas Orientais. Muitos ortodoxos orientais, porém, rejeitam essa classificação, mesmo como um termo genérico, mas ele é amplamente utilizado na literatura históri...
            Read more

            Angular Downloading a file using contenturl with Basic Authentication

            Image
            0 I have a contentUrl when user clicks on that,file should be downloaded. If I try to browse the contentUrl in the browser it asks for Userid and password.I believe this is Basic Authentication.I dont want user to enter UserId and Password so I am passing it Authorization(Please see below code). Url looks some thing like this: http://XXX.XXX.XX.XXX:8080/flowable-rest/service/runtime/tasks/90875/attachments/90555/content let username : string = 'admin'; let pwd : string = 'test'; let headers = new Headers(); headers.set('Accept', 'text/json'); headers.append('Content-Type', 'application/json'); headers.set('Access-Control-Allow-Origin', '*'); headers.set('Access-Control-Allow-Methods','POST, GET, OPTIONS, PUT, DELETE'); head...
            Read more

            Olmecas

            Image
            Monumento 1, uma das quatro cabeças colossais encontradas em La Venta, com altura aproximada de 3 metros Olmecas é a designação do povo e da civilização que estiveram na origem da antiga cultura pré-colombiana da Mesoamérica e que se desenvolveram nas regiões tropicais do centro-sul do atual México durante o pré-clássico, próximo de onde hoje estão localizados os estados mexicanos de Veracruz e Tabasco, no Istmo de Tehuantepec, numa zona designada área nuclear olmeca. A cultura olmeca floresceu nesta região aproximadamente entre 1500 e 400 a.C., [ 1 ] e crê-se que tenha sido a civilização-mãe de todas as civilizações mesoamericanas que se desenvolveram posteriormente. [ 2 ] No entanto, desconhece-se a sua exacta filiação étnica, ainda que existam numerosas hipóteses colocadas para tentar resolver esta questão. O etnónimo olmeca foi cunhado pelos arqueólogos do século XX, e não devem confundir-se com os muito posteriores olmecas-xicalancas que ocuparam vários locais do México...
            Read more