Haskell <<loop>>

Question

使用 getIndex xs y 函数，我想要获取列表 xs 中第一个子列表长度大于 y 的子列表的索引。

输出结果为：

[[],[4],[4,3],[3,5,3],[3,5,5,6,1]]
aufgabe6: <<loop>>

为什么getIndex无法工作？

import Data.List

-- Die Sortierfunktion --
myCompare a b
    | length a < length b = LT
    | otherwise = GT

sortList :: [[a]] -> [[a]]
sortList x = sortBy myCompare x

-- Die Indexfunktion --
getIndex :: [[a]] -> Int -> Int
getIndex [] y = 0
getIndex (x:xs) y
    | length x <= y = 1 + getIndex xs y
    | otherwise = 0
    where (x:xs) = sortList (x:xs)

main = do
    print (sortList [[4],[3,5,3],[4,3],[3,5,5,6,1],[]])
    print (getIndex [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 2)

- XHotSniperX

Answer 1

如何使其终止

在这种情况下，问题出在以下方面

getIndex (x:xs) y
    | length x <= y = 1 + getIndex xs y
    | otherwise = 0
    where (x:xs) = sortList (x:xs)

你混淆了哪个(x:xs)是哪个。你应该这样做：

getIndex zs y
    | length x <= y = 1 + getIndex xs y
    | otherwise = 0
    where (x:xs) = sortList zs

提供

Main> main
[[],[4],[4,3],[3,5,3],[3,5,5,6,1]]
3
*Main> getIndex [[],[2],[4,5]] 1
2
*Main> getIndex [[],[2],[4,5]] 5
3

这将为您提供排序列表中至少长度为y的第一个列表的编号, 这实际上回答了问题“原始列表中长度不超过y的列表有多少个？”

我们如何获取其他信息？

如果您想要从原始列表中获取位置, 您可以使用 zip 将条目与其位置标记：

*Main> zip [1..] [[4],[3,5,3],[4,3],[3,5,5,6,1],[]]
[(1,[4]),(2,[3,5,3]),(3,[4,3]),(4,[3,5,5,6,1]),(5,[])]

让我们创建一个实用函数来处理这些内容：

hasLength likeThis (_,xs) = likeThis (length xs)

我们可以这样使用它：

*Main> hasLength (==4) (1,[1,2,3,4])
True
*Main> filter (hasLength (>=2)) (zip [1..] ["","yo","hi there","?"])
[(2,"yo"),(3,"hi there")]

这意味着现在很容易编写一个函数，它可以给出第一个长度超过y的列表的索引。

whichIsLongerThan xss y = 
    case filter (hasLength (>y)) (zip [1..] xss) of
         [] -> error "nothing long enough" -- change this to 0 or (length xss + 1) if you prefer
         (x:xs) -> fst x

这让我们

*Main> whichIsLongerThan [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 2
2
*Main> whichIsLongerThan [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 3
4
*Main> whichIsLongerThan [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 0
1

更短？

但我们可以使用类似的技巧：

whichIsShorterThan xss y = 
    case filter (hasLength (<y)) (zip [1..] xss) of
         [] -> error "nothing short enough" -- change this to 0 or (length xss + 1) if you prefer
         (x:xs) -> fst x

所以你得到了。

*Main> whichIsShorterThan [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 2
1
*Main> whichIsShorterThan [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 1
5
*Main> whichIsShorterThan [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 0
*** Exception: nothing short enough

普遍适用的

让我们提取其中的共同主题:

whichLength :: (Int -> Bool) -> [[a]] -> Int
whichLength likeThis xss = 
    case filter (hasLength likeThis) (zip [1..] xss) of
         [] -> error "nothing found" -- change this to 0 or (length xss + 1) if you prefer
         (x:xs) -> fst x

所以我们可以这样做。

*Main> whichLength (==5) [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 
4
*Main> whichLength (>2) [[4],[3,5,3],[4,3],[3,5,5,6,1],[]] 
2

- AndrewC

---

非常好的、详尽的回答。我很感激不仅知道了解决方案，还知道了思考过程。 - John F. Miller

Answer 2

你的意思是找到第一个子列表长度大于y的索引吗？如果这不是目标（而且小于y），那么

length x <= y = 1 + getIndex xs y

应该是

length x >= y = 1 + getIndex xs y

此外，(x:xs) = sortList (x:xs)是无限循环, 因为它永远不会结束。如果你想以某种方式对其进行排序，可以采用AndrewC的解决方案。

- zw324

Answer 3

let（以及where）在Haskell中是递归绑定：LHS和RHS都属于（因此引用）同一个新作用域。您的代码等效于

........
getIndex (x:xs) y = 
  let                  -- new, extended scope, containing definitions for 
      (x:xs) = a       --   new variables x, xs, a ... the original vars x, xs
      a = sortList a   --   are inaccessible, __shadowed__ by new definitions
  in                   -- evaluated inside the new, extended scope
    if length x <= y         -- x refers to the new definition
      then 1 + getIndex xs y
      else 0

当x的值被length要求时，它的新定义(x:xs) = a要求a的值，而a的值直接以自身为基础定义，即a = sortList a：

a = sortList a
  = sortList (sortList a)
  = sortList (sortList (sortList a))
  = sortList (sortList (sortList (sortList a)))
  = ....

一个黑洞。

- Will Ness